(DFS) – 特别一点的DFS系列 POJ3009

1.原题:http://poj.org/problem?id=3009。题意是冰壶游戏,给定若干组的地图,W表示宽度(列数)H表示高度(行数)。然后接下来的H行W列就是地图数据。0表示没有障碍 1表示障碍 2表示起点 3表示终点。程序的目的是给定一个起点和一个终点,求出满足下列规则的最小的移动数目。

规则:

A.每次冰壶碰到障碍,可以用捆棍子向上下左右移动,并且冰壶的轨迹沿推出的方向。

B.如果冰壶出界、没有路可走或者是10次移动操作内不能到达终点,那么游戏失败输出-1。否则需要求出最小的移动操作

C.冰壶碰到障碍的话,障碍会消失。

2.思路:可以用DFS相四个方向探测,然后临时标记一下起始点,注意我们要沿着方向走,所以需要一个循环一直探测到没有障碍的位置(如果是之前访问的位置没关系,那肯定会失败。)。如果探测打那个点是障碍,那么临时移除他,然后dfs,深度+1;如果是终点,比较最小值;如果是普通的点,就直接dfs,深度+1。递归的基线条件就是depth(深度)>10(从1开始的)

3.代码:

#include <cstdio>
#include <vector>
#include <algorithm>
enum Node {
	NO = 0, BLOCK, START, GOAL
};
const int MAX_W = 20;
const int MAX_H = 20;
int map[MAX_W][MAX_H];
//int flag[MAX_W][MAX_H];
int res[100] = { 0 };
int w, h;
const int limit = 10;
int minopt = limit + 1;
int dir[4][2] = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } };//四个方向 
bool dfs(int depth, int x, int y)
{
	if (depth >limit)
	{
		//fail the game
		return false;
	}
	int dx, dy;
	for (int i = 0; i<4; ++i)
	{
		dx = x + dir[i][0];
		dy = y + dir[i][1];
		if (dx >= 0 && dx <h && dy >= 0 && dy <w && map[dx][dy] !=BLOCK)
		{
			//合法的点 那么需要项这个方向递增移动到下一个组块之前 然后进行dfs
			int nx = dx, ny = dy;
			for (; nx >= 0 && nx <h && ny >= 0 && ny <w && (map[nx][ny] == NO || map[nx][ny]==START); nx = nx + dir[i][0], ny = ny + dir[i][1])
				;
			
			if (nx <0 || nx >= h || ny <0 || ny >= w)
				continue;
			//if (flag[nx][ny] == 1)//这个根本没什么用 因为冰壶会把之前的进过的位置全部撞开 所以我只需要讨论下一步是否出界或者是撞到块的情况
				//continue;
			if (map[nx][ny] == GOAL)
			{
				minopt = std::min(minopt, depth);
				continue;
			}
			if (map[nx][ny] == BLOCK)
			{
				//HIT IT REMOVE;
				map[nx][ny] = NO;
				//flag[x][y] = 1;
				dfs(depth + 1, nx - dir[i][0], ny - dir[i][1]);
				//flag[x][y] = 0;
				map[nx][ny] = BLOCK;
			}
			else
			{
				//flag[x][y] = 1;
				dfs(depth + 1, nx - dir[i][0], ny - dir[i][1]);
				//flag[x][y] = 0;
			}


		}
	}
}
int main()
{
	int r = 0;
	while (~scanf("%d %d", &w, &h) && w != 0 && h != 0)
	{
		int bx, by;
		for (int i = 0; i<h; ++i)
		{
			for (int j = 0; j<w; ++j)
			{
				scanf("%d", &map[i][j]);
				if (map[i][j] == START)
					bx = i, by = j;
			}

		}
		//地图准备完毕了 
		dfs(1, bx, by);
		if (minopt == limit + 1)
		{
			res[r++] = -1;
		}
		else
		{
			res[r++] = minopt;
		}
		minopt = limit + 1;
	}
	for (int i = 0; i<r; ++i)
	{
		if (res[i] != 0)
			printf("%d\n", res[i]);

	}
	return 0;
}