POJ1979

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can‘t move on red tiles, he can move only on black tiles. 

Write a program to count the number of black tiles which he can reach by repeating the moves described above. 

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20. 

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows. 

‘.‘ - a black tile 
‘#‘ - a red tile 
‘@‘ - a man on a black tile(appears exactly once in a data set) 
The end of the input is indicated by a line consisting of two zeros. 

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

有一个矩形的房间，里面铺满了方形的瓷砖。每一个瓷砖有红色还有黑色两种，人只能站在黑色的瓷砖上不能站在红色的瓷砖上，每次只能走前后左右四个方向的四个瓷砖，计算能够到达的黑色瓷砖的总面积数。

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.

//可走的下一个点
if(x >= 0 && x <= H && y >=0 && y < W && cango[x][y] == ‘.‘ )

这样对于来的每一个点的上下左右做一次判断就ok了

   DFS(p - 1, q);
   DFS(p, q - 1);
   DFS(p, q + 1);
   DFS(p + 1, q);

但是在此之前由于比较挫的算法功力，以及看的比较少的代码，导致写出了下面比较扭曲的代码片段：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_N 20
int W, H;
char a[MAX_N][MAX_N];
int res=1;
bool flag = false;
int dfs(int nx, int ny)
{
	
	//搜索下面
	if(nx>=0 && nx+1<H && ny>=0 && ny<W && a[nx+1][ny] ==‘.‘)
	{	
		nx = nx+1;
		a[nx][ny] = ‘#‘;
		res++;
		flag = true;
		dfs(nx,ny);
	}
	//搜索右面
	 if(nx>=0 && nx<H && ny>=0 && ny+1<W && a[nx][ny+1]==‘.‘)
	{	
		ny = ny +1;
		a[nx][ny] = ‘#‘;
		res++;
		flag = true;
		dfs(nx,ny);
	}
	//搜索上面
	 if(nx-1>=0 && nx<H && ny>=0 && ny<W && a[nx-1][ny] ==‘.‘)
	{	
		nx = nx-1;
		a[nx][ny] = ‘#‘;
		res++;
		flag = true;
		dfs(nx,ny);
	}
	//搜索左面
	 if(nx>=0 && nx<H && ny-1>=0 && ny<W && a[nx][ny-1]==‘.‘)
	{	
		ny = ny-1;
		a[nx][ny] = ‘#‘;
		res++;
		flag = true;
		dfs(nx,ny);
	}
	 if(flag == false)
		 return res;
	
	return res;
}

int main()
{
	int nx=0,ny=0;
	char c;
	int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
	int x,y;
	while(scanf("%d%d\n",&W, &H) && (W || H))
	{
		for(int i=0; i<H; i++)
		{
			for(int j=0; j<W; j++)
			{
				scanf("%c",&a[i][j]);
				if(a[i][j]==‘@‘)
				{
					nx = i;
					ny = j;
					a[nx][ny] = ‘#‘;
				}
			}
			c=getchar();
		}
		
		for(int i = 0; i < 4; i++)
		{
			x = nx + dx[i];
			y = ny + dy[i];
			if(a[x][y]==‘.‘)
			{
				res=dfs(nx,ny);
			}
		}
		printf("%d\n",res);
		res=1;
	}
	//system("PAUSE");
	return 0;
}

//#define LOCAL
#include <stdio.h>
#include <string.h>

#define MAXN 20 + 10

char graph[MAXN][MAXN];
int m, n;
int result;

void DFS(int p, int q);

int main()
{
#ifdef LOCAL
	freopen("C:\\Users\\Administrator\\Desktop\\Temp\\ACMTempIn.txt", "r", stdin);
	//freopen("C:\\Users\\Administrator\\Desktop\\Temp\\ACMTempOut.txt", "w", stdout);
#endif


    int i, j;
    int p, q;
    while(scanf("%d%d", &n, &m) && m != 0)
    {
        // 数据的初始化
        result = 0;
        memset(graph, 0, sizeof(graph));

        // 数据输入
        for(i = 0; i < m; i++)
            for(j = 0; j < n; j++)
            {
                scanf("\n%c", &graph[i][j]);
                if(graph[i][j] == ‘@‘)
                {
                   p = i;
                   q = j;
                   graph[i][j] = ‘.‘;
                }
            }
         // 算法主体
         DFS(p , q);
         
         // 数据输出
         printf("%d\n", result);
    }

    return 0;
}

void DFS(int p, int q)
{
   if(p <= m - 1 && p >= 0 && q >= 0 && q <= n - 1 && graph[p][q] == ‘.‘)
   {
        result++;
        graph[p][q] = ‘#‘;
   }else {
        return;
   }
   
   DFS(p - 1, q);
   DFS(p, q - 1);
   DFS(p, q + 1);
   DFS(p + 1, q);
}

瞬间高大上了，呀呀，keep fighting~