BFS样例能过,0分求调

P1141 01迷宫

_hsk121212_ @ 2024-02-22 12:00:20

RT.

#include<bits/stdc++.h>
using namespace std;
struct point{
    int x,y;
}q[1000001];
char g[1001][1001];
int n,m,sx,sy;
bool us[1001][1001];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)   scanf("%s%*c",g[i]+1);
    while(m--){
        memset(us,0,sizeof(us));
        memset(q,0,sizeof(q));
        int k=0,e=1,f=1;
        scanf("%d %d",&sx,&sy);
        q[1].x=sx,q[1].y=sy;
        while(f<=e){
            point u=q[f++];
            for(int i=0;i<4;i++){
                point v;
                v.x=u.x+dx[i],v.y=u.y+dy[i];
                if(v.x<1||v.x>n||v.y<1||v.y>n)  continue;
                if(us[v.y][v.x])    continue;
                if(g[v.y][v.x]==g[u.y][u.x])    continue;
                q[++e]=v;
                us[v.y][v.x]=1;
            }
        }`
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(us[j][i])    k++;
            }
        }
        printf("%d\n",k);
    }
    return 0;
}

by masonxiong @ 2024-02-23 15:09:16

复杂度严重不对,光 bfs 初始化的复杂度就达到了 O(n^2m),直接爆了

这题得动动脑子,直接暴力肯定挂


by zzx1228 @ 2024-03-07 16:31:28

给个思路吧:

应该是先找连通块,整体赋值,最后的询问提前记录可以直接给答案


|