P1141 01迷宫

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<string.h>
 5 #include<algorithm>
 6 using namespace std;
 7 #define re register
 8 
 9 typedef pair<int,int> P;
10 int n,m;
11 int mapp[1005][1005];        //存迷宫 
12 int flag[1005][1005];        //标记        不同连通图上的标记值不同 
13 int sx[100005],sy[100005];    //起点和终点 
14 int dx[4]={0,1,0,-1};
15 int dy[4]={1,0,-1,0};
16 int ans[100000000];            //储存结果 尽量开的大一些 
17 int bfs(int x,int y,int t){
18     int sum=0;                //记录步数 
19     queue<P> que;
20     que.push(P(x,y));        //第一个结点入栈
21     flag[x][y]=t;            //代表访问过
22     
23     while(!que.empty()){
24         P cur=que.front();
25         que.pop();
26         int tx=cur.first;
27         int ty=cur.second;
28         sum++;
29         
30         if(mapp[tx][ty]==1){        //则将0进行入队 四个方向搜索 
31             for(int i=0;i<4;i++){
32                 int mx=tx+dx[i];
33                 int my=ty+dy[i];
34                 if(mapp[mx][my]==0&&flag[mx][my]==0&&mx>=1&&mx<=n&&my>=1&&my<=n){    //没访问过 
35                     que.push(P(mx,my));
36                     flag[mx][my]=t;
37                 }
38             }
39         }else if(mapp[tx][ty]==0){
40             for(int i=0;i<4;i++){
41                 int mx=tx+dx[i];
42                 int my=ty+dy[i];
43                 if(mapp[mx][my]==1&&flag[mx][my]==0&&mx>=1&&mx<=n&&my>=1&&my<=n){    //没访问过 
44                     que.push(P(mx,my));
45                     flag[mx][my]=t;
46                 }
47             }
48         }
49     }
50     return sum;
51 }
52 int main(){
53     cin>>n>>m;
54     for(re int i=1;i<=n;i++){
55         for(re int j=1;j<=n;j++){
56             char temp;
57             cin>>temp;
58             mapp[i][j]=temp-‘0‘;
59         }
60     }
61     
62     int t=0;                //标记值为1 2 3…… 
63     for(int i=1;i<=n;i++){            //对迷宫所有点都搜索 
64         for(int j=1;j<=n;j++){
65             if(flag[i][j])    continue;        //表示标记过，不需要再进行bfs
66             t++; 
67             ans[t]=bfs(i,j,t);        //ans[t]保存标记值为t的连通图的节点数量 
68         }
69     }
70     
71     for(re int i=1;i<=m;i++){        //卡时间的关键点 
72         scanf("%d%d",&sx[i],&sy[i]);        //起始坐标     
73         int x=sx[i],y=sy[i];     
74         printf("%d\n",ans[flag[x][y]]);
75     }
76     
77     return 0;
78 }