POJ 1979 Red and Black 《挑战程序设计竞赛(第2版)》练习题答案

2.1 最基础的“穷竭搜索” 深度优先搜索

POJ 1979 Red and Black

  一个房间上有红色的瓦和黑色的瓦片，给出红瓦和黑瓦的位置和人所占的位置，求人最多能走过多少片瓦？ 
（条件为：人行走过程中只能走黑瓦，且人的初始位置为黑瓦） 
输入描述：输入的字符里面只有三种字符： 
           “@”—–表示人（只能有一个该字符） 
           “.”—–表示黑瓦 
           “#”—–表示红瓦 

样例： 
Sample Input 

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

Sample Output 

45 

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
using namespace std;

#define MAX_W 20
#define MAX_H 20
char room[MAX_W][MAX_H];
int W, H;
const int direction[4][2] = {
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1},
};

int step = 0;

int dfs(const int& x, const int& y)
{
	room[x][y] = '#';
	++step;
	for (int i = 0; i < 4; ++i)
	{
		int nx = x + direction[i][0];
		int ny = y + direction[i][1];
		if (nx >= 0 && nx < W && ny >= 0 && ny < H && room[nx][ny] == '.')
		{
			dfs(nx, ny);
		}
	}

	return step;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	while (cin >> W >> H, W > 0)
	{
		step = 0;
		int x, y;
		for (y = 0; y < H; ++y)
		{
			for (x = 0; x < W; ++x)
			{
				cin >> room[x][y];
			}
		}

		bool found = false;
		for (x = 0; x < W; ++x)
		{
			for (y = 0; y < H; ++y)
			{
				if (room[x][y] == '@')
				{
					found = true;
					break;
				}
			}
			if (found)
			{
				break;
			}
		}

		cout << dfs(x, y) << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1979 Red and Black 《挑战程序设计竞赛(第2版)》练习题答案