01迷宫求助大佬！！！

Mars_wq @ 2023-12-01 22:06:38

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long 
using namespace std;
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
bool vis[1001][1001];
ll step[1001][1001];
ll ans;
char a[10015][1001];
ll n,m;
void bfs(ll x,ll y){
    memset(step,0x3f,sizeof step);
    queue<pair<ll,ll> >q;
    q.push(make_pair(x,y));
    vis[x][y]=1;
    step[x][y]=0;
    while(!q.empty()){
        pair<ll,ll> tmp=q.front();
        q.pop();
        ans++;
        for(ll i=0;i<4;i++){
            ll nx=tmp.first+dx[i],ny=tmp.second+dy[i];
            if(nx<1||nx>n||ny<1||ny>n)continue;
            if(vis[nx][ny]==1||a[tmp.first][tmp.second]==a[nx][ny])continue;
            vis[nx][ny]=1;
            q.push(make_pair(nx,ny));
            step[nx][ny]=step[tmp.first][tmp.second]+1;
        }
    }
}
int main(){
    scanf("%lld %lld", &n, &m); 
    char c;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            cin >> c;
            a[i][j] = c - '0';
        }
    }
    ll x,y;
    for(ll i=1;i<=m;i++){
        memset(vis,0,sizeof vis);
        cin>>x>>y;
        ans=0;
        bfs(x,y);
        printf("%lld\n", ans);
    }
    return 0;
}

by Sinktank @ 2023-12-02 03:08:12

1. 一个连通块只需跑一次BFS，因为其中所有格子的结果都相同。把连通的格子对应到一个答案上即可。
2. 做了上面的优化，可以发现vis和step不需要memset了，因为上面的优化中，一个连通块只跑一遍。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long 
using namespace std;
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
bool vis[1001][1001];
ll step[1001][1001];
ll ans;
char a[10015][1001];
ll n,m;
int mem[1001][1001],cnt,val[1000001];
//mem[i][j]记忆了坐标i,j的答案，cnt表示当前连通块编号，val[i]表示编号为i的连通块答案是多少
//val要开到n^2，因为最极端情况全为1，就是n^2个连通块
void bfs(ll x,ll y){
    if(mem[x][y]){
        ans=val[mem[x][y]];
        return;
    }
    cnt++;//当前格不在之前的连通块中，说明开启了一个新块，计数
    //memset(step,0x3f,sizeof step);
    queue<pair<ll,ll> >q;
    q.push(make_pair(x,y));
    vis[x][y]=1;
    step[x][y]=0;
    while(!q.empty()){
        pair<ll,ll> tmp=q.front();
        mem[tmp.first][tmp.second]=cnt;//记录当前格在第cnt个连通块中
        q.pop();
        //ans++;
        val[cnt]++;//计数也是在val中记
        for(ll i=0;i<4;i++){
            ll nx=tmp.first+dx[i],ny=tmp.second+dy[i];
            if(nx<1||nx>n||ny<1||ny>n)continue;
            if(vis[nx][ny]==1||a[tmp.first][tmp.second]==a[nx][ny])continue;
            vis[nx][ny]=1;
            q.push(make_pair(nx,ny));
            mem[nx][ny]=cnt;
        }
    }
    ans=val[cnt];//设置ans
}
int main(){
    scanf("%lld %lld", &n, &m); 
    char c;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            cin >> c;
            a[i][j] = c - '0';
        }
    }
    ll x,y;
    for(ll i=1;i<=m;i++){
        //memset(vis,0,sizeof vis);
        cin>>x>>y;
        ans=0;
        bfs(x,y);
        printf("%lld\n", ans);
    }
    return 0;
}