ZOJ-2165* 迷宫问题

2165：给出初始位置，给出不可走区域，求能够到达的位置个数。

Sample Input

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



Sample Output

45
59
6
13



思路:DFS遍历。上下左右按一定顺序递归，全局变量进行统计。
注意二维数组的第一个下标对应高度值，第二个下标对应宽度值。

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

int map[21][21];
int sum;
int ori[4][2]={ 
	0,1,//right
	0,-1,//left
	1,0,//up
	-1,0 //down
};

bool legal(int x,int y,int w,int h)
{
	if(x>=h||x<0) 
		return false;
	if(y>=w||y<0) 
		return false;
	else 
		return true;
}

void DFS(int x,int y,int w,int h)
{
	int tx,ty,i;
	sum++;
	map[x][y]=1; // no more visit

	for(i=0;i<4;i++)
	{
		tx=x+ori[i][0];
		ty=y+ori[i][1];
		if(!map[tx][ty]&&legal(tx,ty,w,h))
		{
			DFS(tx,ty,w,h);
		}
	}
}


int main()
{
	int W;
	int H;
	int x;
	int y;
	char c;

	while(1)
	{
		scanf("%d%d",&W,&H);
		
		if((W||H)==0)  //= is higher than or
			break;
		
		memset(map,0,sizeof(map));
		for(int i=0;i<H;i++)
		{
			getchar();
			for(int j=0;j<W;j++)
			{
				c=getchar();
				if(c=='#')
				{
					map[i][j]=1;
				}
				else if(c=='@')
				{
					x=i;
					y=j;
				}
			}
		}

		sum=0;
		DFS(x,y,W,H);
		printf("%d\n",sum);


	}
}