用dfs遍历联通块（优化）

一、题目（CF 598D）

输入一个n x m的字符矩阵，求从某个空点出发，能碰到多少面墙壁，总共询问k次。(3 ≤m,n ≤1000,1 ≤ k ≤ min(nm,100 000))

二、解题思路

用DFS找连通分量：从每个“.”格子出发，递归遍历与之相邻的“*”格子，且写上相同的联通分量（即代码中的blocks数组），同时统计该联通分量边界墙壁面数。由于存在多次查询，我们用blocks[i][j]记录格子(i,j)所在的联通分量标号，用res[i]表示联通分量i的边界墙壁面数。

三、代码实现

 #include<stdio.h>

 #include<iostream>

 #include<string.h>

 #include<stdbool.h>

 using namespace std;

 const int maxn =  + ;

 const int maxm =  + ;

 const int maxk =  + ;

 const int maxx =  + ;

 int n, m;

 char maze[maxn][maxm];

 bool vis[maxn][maxm];

 int blocks[maxn][maxm];

 int res[maxx];

 int dx[] = { -,,, }, dy[] = { ,,,- };

 int flag = ;

 void dfs(int x, int y, int flag,int& sum)   //sum传引用

 {

     vis[x][y] = true;

     blocks[x][y] = flag;

     for (int i = ; i < ; i++)

     {

         int xx = x + dx[i]; int yy = y + dy[i];

         if (xx >=  && xx < n && yy >=  && yy < m && (!vis[xx][yy]))

         {

             if (maze[xx][yy] == '*')

                 sum++;

             else

                 dfs(xx, yy, flag,sum);

         }

     }

 }

 int main()

 {

     int k;

     scanf("%d%d%d", &n, &m, &k);

     memset(vis, , sizeof(vis));

     for (int i = ; i < n; i++)

         for (int j = ; j < m; j++)

             cin >> maze[i][j];

     for (int i = ; i < n; i++)

         for (int j = ; j < m; j++)

         {

             if (maze[i][j] == '.' && (!vis[i][j]))

             {

                 int sum = ;

                 dfs(i, j, ++flag,sum);

                 res[flag] = sum;

             }

         }

     while (k--)

     {

         int sx, sy;

         scanf("%d%d", &sx, &sy);

         printf("%d\n", res[blocks[sx - ][sy - ]]);

     }

     return ;

 }