POJ 1979 深度优先搜索

题意：有红色和黑色的格子，只能走黑色的，问从起始位置出发，最多能走到达多少块黑色格子。

分析：相当于走迷宫，黑色格子是路，红色格子是墙，每次到达一个未到达过的格子时计数，原点也算是一个。每次可以走上下左右四个方向，用深度优先遍历从原点起始，一直到遍历所有能到达的格子。需要注意的是，不要重复走同一个格子，可以采取数组标记已走过的格子，但这里只需简单将已走过的格子标记为红色就可以达到目的，因为红色的格子也不可走。

C++代码：

 #include <cstdio>

 const int MAX_W = ;

 const int MAX_H = ;

 //输入

 int W;

 int H;

 char maze[MAX_H][MAX_W + ];

 //4个方向

 const int d[][] = {{, -}, {, }, {, }, {-, }};

 int dfs(int x, int y){

     int ans = ;

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

         int nx = x + d[i][], ny = y + d[i][];

         if( <= nx && nx < H &&  <= ny && ny < W && maze[nx][ny] == '.'){

             ans ++;

             maze[nx][ny] = '#';

             ans += dfs(nx, ny);

         }

     }

     return ans;

 }

 void solve(){

     //找出起始位置

     int sx, sy;

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

         for(int j = ; j < W; j ++){

             if(maze[i][j] == '@'){

                 sx = i;

                 sy = j;

                 break;

             }

         }

     }

     //深度优先遍历，每到一个新位置就计数

     int ans =  + dfs(sx, sy);

     printf("%d\n", ans);

 }

 int main(int argc, char const *argv[]){

     while(scanf("%d %d", &W, &H)){

         if(W ==  && H == ) break;

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

             scanf("%s", maze[i]);

         solve();

     }

     return ;

 }