Red and Black---hdu1312（dfs）

2015-04-07http://acm.hdu.edu.cn/showproblem.php?pid=1312

Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

Sample Output
45
59
6
13
////////////////////////////////////////
题意：
.代表黑色瓷砖；
#代表红色瓷砖；
@是起始位置；
求的是从起始位置开始所能走的黑色的块的个数，不能跳过红色；

用递归的方法一次找到上下左右的所有有关的黑色瓷砖；

代码如下：

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

#define maxn 105

char G[maxn][maxn];
int m, n;

int f(int x, int y)
{

    if(x<0 || x>=m || y<0 || y>=n)//如果当前位置超出矩阵范围，则返回0
        return 0;

    else if(G[x][y] == '#')//否则如果当前位置是白色方格，则返回0
        return 0;

    else//否则
    {
//将走过的瓷砖做标记；
        G[x][y] = '#';
//递归处理
        return 1+f(x-1, y)+f(x+1, y)+f(x, y-1)+f(x, y+1);
    }
}

int main()
{

    int i, j, x, y;

    cin >> m >> n;

    for(i=0; i<m; i++)
        for(j=0; j<n; j++)
        {
            cin >> G[i][j];

            if(G[i][j] == '@')
                x=i, y=j;
        }

    int ans = f(x, y);

    cout << ans <<endl;

    return 0;
}

 1 #include<iostream>
 2 #include<string.h>
 3 #define N 25
 4 using namespace std;
 5 char maps[N][N];
 6 int m,n,ans;
 7 int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };
 8 
 9 void dfs(int x,int y)
10 {
11     int i;
12     if(x>=m||x<0||y>=n||y<0)
13         return ;
14     if(maps[x][y]=='#')
15         return ;
16     else
17     {
18         maps[x][y]='#';
19         ans++;
20         for(i=0;i<4;i++)
21         {
22                 dfs(x+dir[i][0],y+dir[i][1]);            
23         }
24     }
25 }
26 
27 int main()
28 {
29     int i,x,y,j;
30     while(scanf("%d%d",&n,&m),m+n)
31     {
32         ans=0;
33         memset(maps,0,sizeof(maps));
34         for(i=0;i<m;i++)
35         {
36             for(j=0;j<n;j++)
37             {
38                 cin>>maps[i][j];
39                 if(maps[i][j]=='@')
40                 {
41                     x=i,y=j;
42                 }
43             }
44         }
45         dfs(x,y);
46         printf("%d
",ans);
47     }
48     return 0;
49 }