poj 3009 Curling 2.0 dfs

缘起

日常水题 poj 3009 Curling 2.0

分析

题目到是挺绕的，但是看仔细之后其实是水题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
给一块矩形的冰球练习板. 上面有一些冰块，以及一个出发点S和终点G. 要从S到G. 如果冰球出界，则游戏失败. 
如果碰到冰块，则会将冰块撞碎（冰块消失）.然后冰球停在撞击前的位置. 问能不能从S到G，如果能到, 输出
最少步骤. 如果不能输出 -1

【输入】
多样例， 每个样例以w和h开头. 2 <= w <= 20, 1 <= h <= 20. 表示练习板的宽度和高度. 然后是h*w的
二维整数数组， 0表示空白，1表示冰块，2表示开始位置，3表示结束位置. 输入保证开始!=结束, 而且都不会是
冰块位置. 以(0,0)表示输入结束.

【输出】
如果能到，则输出最少步骤数，如果不能到达，输出-1

【样例输入】
2 1
3 2
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
6 1
1 1 2 1 1 3
6 1
1 0 2 1 1 3
12 1
2 0 1 1 1 1 1 1 1 1 1 3
13 1
2 0 1 1 1 1 1 1 1 1 1 1 3
0 0

【样例输出】
1
4
-1
4
10
-1

【限制】
Time Limit: 1000MS
Memory Limit: 65536K

【来源】
Japan 2006 Domestic

dfs即可，注意，dfs是搜索，不是遍历. 所以如果撞碎了冰块要恢复冰块.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//#include "stdafx.h"

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

int w,h, map[25][25],ans,si,sj,gi,gj; // (si,sj)是起点, (gi,gj)是终点
const int directon[4][2] = {{0,-1},{0,1},{-1,0},{1,0}}; // 四个方向 上下左右

bool ok(int x, int y, int i,int &nxtx,int &nxty,bool &flag) // (x,y)处沿着 direction[i]进行拓展, (nxtx,nxty)是新的位置
{
	if (x+directon[i][0]<0||x+directon[i][0]>=h || y+directon[i][1]<0|| y+directon[i][1]>=w || map[x+directon[i][0]][y+directon[i][1]]==1)
	{
		return false; // 如果紧邻障碍物, 返回false
	}
	int nx,ny;
	while(1)
	{
		nx = x+directon[i][0];
		ny = y+directon[i][1]; // 移动到(nx,ny)
		if (nx==gi && ny == gj) // 如果这条道上遇到了终点
		{
			nxtx = nx;
			nxty = ny;
			return true;
		}
		if (nx<0||nx>=h || ny<0|| ny>=w) // 如果下一步越界
		{
			return false;
		}
		if (map[nx][ny]==1) // 如果下一步遇到了冰块
		{
			nxtx = x;
			nxty = y;
			map[nx][ny] = 0; //冰块被撞碎了
			flag = true;
			return true; // 则记录下位置,返回true
		}
		x = nx;
		y = ny;
	}
}

void dfs(int x, int y, int step) // 来到了(x,y) 迄今已经走了step步
{
	if (step>10 || step>=ans) // 剪枝
	{
		return;
	}
	if (x == gi && y == gj) // 找到一条路了
	{
		if (ans>step)
		{
			ans = step;
		}
		return;
	}
	for (int i = 0,nxtx,nxty; i<4; i++) // 开始沿着上下左右4个方向拓展
	{
		bool flag = false; // 移动沿途是否撞碎了冰块
		if (ok(x,y,i,nxtx, nxty, flag)) // 如果可以沿着第i个方向进行拓展的话
		{
			dfs(nxtx, nxty, step+1);
			if (flag) // 如果撞碎了冰块是要"赔"的, 囧~ 而冰块恰好就在(nxtx, ntxy)的沿着i方向的下一步,因为这是搜索不是遍历, 所以要还原回去
			{
				map[nxtx+directon[i][0]][nxty+directon[i][1]] = 1;
			}
		}
			
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &w, &h), w||h)
	{
		ans = 0x3f3f3f3f;
		for (int i = 0; i<h; i++) // i是所在行, j是所在列
		{
			for (int j = 0; j<w; j++)
			{
				scanf("%d", &map[i][j]);
				if (map[i][j]==2)
				{
					si = i;
					sj = j;
				}
				else if (map[i][j] == 3)
				{
					gi = i;
					gj = j;
				}
			}
		}
		dfs(si,sj,0); // 从 (si,sj)出发开始dfs
		if (ans>10)
		{
			ans = -1;
		}
		printf("%d\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 110ms
Memory 92kB
Length 1973
Lang C++
Submitted 2019-08-23 13:38:11
Shared
RemoteRunId 20791532