洛谷P1141 01迷宫【bfs】-白红宇

洛谷P1141 01迷宫【bfs】

阅读量：5329 次

发布时间：2019-06-14

本文共 1702 字，大约阅读时间需要 5 分钟。

题目链接：

题意：

有一个填了0和1的n*n的格子，只能0走到1，1走到0

有m组询问（数据量是1e5），问某一个格子可以到达的格子数。

思路：

刚开始一直在想记忆化搜索。某一个格子走过了之后的格子数记下来，之后访问到的时候加上。

但是这样会重复的。比如（x,y）走到（i,j)，他们能走到的格子是有交集的，并不是包含的关系。

应该要想到连通块。

给定的这个图形成了若干的连通块。我们只需要预处理一下这些连通块，对于每次询问查询他对应的连通块的大小就行了。

1 #include
     
       2 #include
      
        3 #include
        4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 11 using namespace std;12 typedef pair
              
                pr;13 14 int n, m;15 int mat[1005][1005];16 int dx[4] = { 1, -1, 0, 0};17 int dy[4] = { 0, 0, 1, -1};18 19 int id[1005][1005];20 int cnt[1000005];21 22 bool check(pr p)23 {24 int i = p.first, j = p.second;25 return (i > 0 && i <= n && j > 0 && j <= n);26 }27 28 void bfs(int i, int j, int k)29 {30 int c = 1;31 queue
               
                que;32 pr st = make_pair(i, j);33 que.push(st);34 id[i][j] = k;35 while(!que.empty()){36 pr now = que.front();que.pop();37 for(int i = 0; i < 4; i++){38 pr tmp = make_pair(now.first + dx[i], now.second + dy[i]);39 if(check(tmp) && !id[tmp.first][tmp.second] && mat[tmp.first][tmp.second] ^ mat[now.first][now.second]){40 id[tmp.first][tmp.second] = k;41 que.push(tmp);42 c++;43 }44 }45 }46 cnt[k] = c;47 }48 49 int main()50 {51 scanf("%d%d", &n, &m);52 for(int i = 1; i <= n; i++){53 char s[1005];54 scanf("%s", s);55 for(int j = 1; j <= n; j++){56 mat[i][j] = s[j - 1] - '0';57 }58 }59 int now_id = 1;60 for(int i = 1; i <= n; i++){61 for(int j = 1; j <= n; j++){62 if(!id[i][j]){63 bfs(i, j, now_id);64 now_id++;65 }66 }67 }68 69 for(int i = 0; i < m; i++){70 int x, y;71 scanf("%d%d", &x, &y);72 printf("%d\n", cnt[id[x][y]]);73 }74 75 return 0;76 }