OI

【搜索】01迷宫

一看题目标注的高性能就知道不能询问一次搜一次。因为一个联通块的答案是相同的，所以一个块只要搜一次，再标记上就行了。

标记用了个队列记录再一次标记，怕搜晕了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<stdio.h>
struct node{
    int x,y;
};
struct node queue[1000005]={0};
int n,m;
int map[1005][1005]={0};
int ans[1005][1005]={0};
int dx[10]={0,0,1,-1},
    dy[10]={1,-1,0,0};
int cnt;
void dfs(int x,int y){
    int j,tx,ty;
    queue[cnt].x=x;
    queue[cnt].y=y;
    for(j=0;j<4;j++){
        tx=x+dx[j];
        ty=y+dy[j];
        if(ans[tx][ty]==-1&&tx>=1&&ty>=1&&tx<=n&&ty<=n&&map[x][y]!=map[tx][ty]){
          ans[tx][ty]=-2;
          cnt++;
          dfs(tx,ty);
        }
    }
    
}

void fill(int n){
    int i;
    if(n==1)n++;
    for(i=1;i<=n;i++)
      ans[queue[i].x][queue[i].y]=n-1;
}

int main(){ 
    int i,j;
    int x,y;
    char temp[1005];
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
      scanf("%s",temp);
      for(j=1;j<=n;j++){
        map[i][j]=temp[j-1]-'0';
        ans[i][j]=-1;
      }
    }
    
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(ans[x][y]!=-1)printf("%d\n",ans[x][y]);
        else{
          cnt=1;
          dfs(x,y);
          fill(cnt);
          printf("%d\n",ans[x][y]);
        }
    }
    
    return 0;
}