bfs怎么写记忆化，T了

Acwing_zbz @ 2024-03-27 17:33:31

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
char g[N][N];
bool st[N][N];
int n,m,dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int bfs(int x,int y)
{
    int res=1;
    queue<PII> q;
    q.push({x,y});
    st[x][y]=true;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int a=dx[i]+t.first,b=dy[i]+t.second;
            if(a>n||b>n||a<1||b<1||g[a][b]==g[t.first][t.second]||st[a][b])continue;
            st[a][b]=true;
            q.push({a,b});
            res++;
        }
    }
    return res;
}
int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        cin>>g[i][j];
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        memset(st,false,sizeof st);
        cout<<bfs(x,y)<<endl;
    }
    return 0;
 } 

by chen_kun @ 2024-03-27 17:38:11

@Acwing_zbz 数据太多了每次都搜会TLE，可以用连通块的思想

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,tx,ty,dx[5]={-1,1,0,0},dy[5]={0,0,-1,1},vis[1111][1111],ans,sum[1111],t=1,av[1111][1111];
char a[1111][1111];
struct node{
    int x,y;
};
void bfs(int x0,int y0){
    vis[x0][y0]=1;
    queue<node>q;
    q.push({x0,y0});
    ans=1;
    while(!q.empty()){
        x=q.front().x;
        y=q.front().y;
        q.pop();
        av[x][y]=t;
        for(int i=0;i<4;i++){
            tx=x+dx[i];
            ty=y+dy[i];
            if(a[x][y]!=a[tx][ty]&&vis[tx][ty]==0&&tx>=1&&tx<=n&&ty>=1&&ty<=n) vis[tx][ty]=1,q.push({tx,ty}),ans++;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i][j]==0){
                bfs(i,j);
                sum[t]=ans;
                t++;
            }
        }
    }
    while(m--){
        cin>>x>>y;
        cout<<sum[av[x][y]]<<endl;
    }
    return 0;
}

by Acwing_zbz @ 2024-03-27 17:42:46

@chen_kun 大佬如果用记忆化的话该怎么存储呢？