70分 TLE 超时

181zs @ 2024-07-11 11:45:54

#include <bits/stdc++.h>
using namespace std;
int n, m;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
char s[1005][1005];
int ans = 0,vis[1005][1005];
void dfs(int x,int y){
    ans++;  
    for(int i=0;i<=3;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<=n&&nx>=1&&ny<=n&&ny>=1&&s[nx][ny]!=s[x][y]&&!vis[nx][ny]){
            vis[nx][ny]=1;
            dfs(nx,ny);
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> s[i][j];
        }
    }

    for (int i = 1; i <= m; i++) {
        memset(vis,0,sizeof(vis));
        ans = 0;
        int x, y;
        cin >> x >> y;
        vis[x][y]=1;
        dfs(x, y);
        cout << ans << endl;
    }

    return 0;
}

by gaomingyang101011 @ 2024-07-11 17:58:13

你可以用一个二维数组在每次搜索后将搜索时能走到的点到的点都标记为他们能走到的点的个数，后面在输入后判断如果之前目标点被标记过就直接输出就行了。

by wa_wa_wa_wa @ 2024-07-11 20:10:41

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
    int x,y;
};
int a[1005][1005],vis[1005][1005],anss[1005][1005];
const int movex[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < n; j++){
            a[i][j+1] = s[j]-'0';
        }
    }
    int s[2];
    s[0] = 1;
    s[1] = 0;
    while(m--){
        queue<node>q;
        queue<node>q2; 
        int x,y;
        scanf("%d%d",&x,&y);
        if(anss[x][y]){
            printf("%d\n",anss[x][y]);
            continue;
        }
        //for(int i = 1; i <= n; i++)
          //  for(int j = 1; j <= n; j++)
            //    vis[i][j] = 0;
        //memset(vis,0,sizeof(vis));
        q.push((node){x,y});
        vis[x][y] = 1;
        int ans = 1;
        while(q.size()){
            node tmp = q.front();   
            q.pop();
            for(int i = 0;i < 4; i++){
                int xx = tmp.x+movex[i][0];
                int yy = tmp.y+movex[i][1];
                if(xx > n || xx < 1 || yy > n || yy < 1 || vis[xx][yy] || a[xx][yy] != s[a[tmp.x][tmp.y]]){
                    continue;
                }
                ans++;
                vis[xx][yy] = 1;
                q.push((node){xx,yy});
                q2.push((node){xx,yy});
            }
        }
        anss[x][y] = ans;
        while(q2.size()){
            anss[q2.front().x][q2.front().y] = ans;
            q2.pop();
        }
        printf("%d\n",ans);
    }
    return 0;
}

by wa_wa_wa_wa @ 2024-07-11 20:10:55

@181zs

by 181zs @ 2024-07-16 19:07:53

@wa_wa_wa_wa谢谢你