70分求助!!!

P1141 01迷宫

sun1112013 @ 2023-12-13 20:20:31


#include<bits/stdc++.h>
using namespace std;
const int N=1005;
char a[N][N];
int n,t,step=1;
int dir[4][2]={-1,0,1,0,0,-1,0,1};
bool vis[N][N];
void dfs(int x,int y){
    for(int i=0;i<4;i++){
        int bx=x+dir[i][0],by=y+dir[i][1];
        if(bx<0||bx>=n||by<0||by>=n) continue;
        if(vis[bx][by]) continue;
        if(a[x][y]==a[bx][by]) continue;
        vis[bx][by]=1;
        step++;
        dfs(bx,by);
    }
}
int main(){
    cin>>n>>t;
    for(int i=0;i<n;i++){
        scanf("%s",a[i]);
    }
    while(t--){
        memset(vis, 0, sizeof(vis));
        int x,y;
        scanf("%d%d",&x,&y);
        vis[x-1][y-1]=1;
        dfs(x-1,y-1);
        printf("%d\n",step);
        step=1;
    }
    return 0;
}

by gaozeju @ 2023-12-13 20:38:03

根据查询,你的问题是TLE。
这题只用查找一遍就可以了。因为答案是固定的,所以你可以用一个数组存下所有点的答案,然后O(1)查询。
或者,每次询问,如果当前点有答案了,直接输出,没有则计算。计算完后将所有联通的点打上同样的答案。
理论时间复杂度是O(n+m)的。
拿样例来说,你只需要第一次计算完毕后,将4个点全部打上4。下次查找直接输出4。


by sun1112013 @ 2023-12-14 21:04:56

@gaozeju_luogu 问题已找出 谢谢dalao


|