// 平时用栈来模拟回溯,这里我不用栈而用队列且不回溯也不深搜
// 如有错误之处,望大牛提点迷津,谢谢

#include <iostream>
using namespace std;

const int N = 20;

int move[4][4]={{0,-1}, {0,1}, {-1,0}, {1,0}};

bool Place(char room[][20], int i, int j, int w, int h) // 判断当前地点是否合格
{
	if (i>=0 && i<=w-1 && j>=0 && j<=h-1 && room[i][j]=='.')
	{
		return true;
	}
	else
	{
		return false;
	}
	
}

struct Node
{
	int i;
	int j;
};

int main()
{
	
	char room[N][N];
	Node queue[N*N]={0};
	int front; 
	int tail ;
	
	int count= 0;
        int w, h;
	int i, j;
	int mani, manj; // 标记人开始站的地点
	int way; // 移动路线

	while (cin>>h>>w && w!=0 && h!=0)
	{
		count = 0;
		memset(room, 0, sizeof(room));
		memset(queue, 0, sizeof(queue)); // 初始化时清空队列,RE过一次
		front = tail = 0;                // 队头队尾也要初始化,RE过一次

		for (i=0; i<=w-1; i++)   // 处理输入
		{
			for (j=0; j<=h-1; j++)
			{
				cin>>room[i][j];
				if (room[i][j] =='@')
				{
					mani = i;
					manj = j;
				}
			}
		}
		
		queue[tail].i = mani; // 将人所站的地点入队
		queue[tail].j = manj;
		room[mani][manj] = '!'; // 对room进行标记
		tail++;
		count++;
		
		Node temp;
		while (front != tail) // 如果队列为空,则表示将一个连通的地点区域都遍历完了
		{
			temp = queue[front]; 
			front++;   // 出队
			
			for (way=0; way<=4-1; way++)
			{
				if (Place(room, temp.i+move[way][0], temp.j+move[way][1], w, h))
				{
					queue[tail].i = temp.i+move[way][0]; // 出队之后,将没有遍历过的地点入队
					queue[tail].j = temp.j+move[way][1];

					room[queue[tail].i][queue[tail].j] = '!';
					tail++;
					count++;
				}
				
			}
		}
		cout<<count<<endl;
		
	}
	return 0;
}

• Re:雁过留声——后缀数组+扫描 (1801) 200831000719 2010-04-07 22:09:38