水管工游戏

发表于

题目

一块矩形土地被分为N*M的单位正方形，现在这块土地上已经埋设有一些水管，水管将从坐标为(1,1)左上角左部边缘，延伸到(N,M)右下角右部边缘。每种管道将占据一个单位正方形土地。你现在可以旋转这些管道，使得构成一个管道系统，即创造一条从(1,1)到(N,M)的连通管道。标有树木的方格表示这里没有管道。障碍物用0表示。我们可以旋转其中的一些管道，使之构成一个连通的管道系统。如果通过旋转管道可以使之构成一个连通的管道系统，就输出铺设的路径，否则输出impossible。

avatar

avatar

avatar

输入

例如：
5 4
5 3 5 3
1 5 3 0
2 3 5 1
6 1 1 5
1 5 5 4

输出

（1,1）（1,2）（2,2）（3,2）（3,3）（3,4）（4,4）（5,4）

代码

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<stack>
using namespace std;

typedef struct node {
	int x;
	int y;
} node;

int length_x = 4, length_y = 5;
int map[5][4] = { { 5,3,5,3 },{ 1,5,3,0 },{ 2,3,5,1 },{ 6,1,1,5 },{ 1,5,5,4 } };
int book[5][4];
node start, target;
bool flag = false;
stack<node> output_stack;

void findPath(node now, int district) {

	if (now.y == target.y && now.x == target.x + 1)
	{
		flag = true;
		while (!output_stack.empty())
		{
			cout << "(" << output_stack.top().x << "," << output_stack.top().y << ")" << endl;
			output_stack.pop();
		}
		return;
	}

	if (now.x >= length_x || now.x < 0 || now.y >= length_y || now.y < 0)
	{
		return;
	}

	if (map[now.y][now.x] == 0)
	{
		return;
	}

	if (book[now.y][now.x] == 1)
	{
		return;
	}

	book[now.y][now.x] = 1;
	output_stack.push(now);

	if (map[now.y][now.x] > 4 && map[now.y][now.x] < 7)
	{
		if (district == 1)
		{
			now.y += 1;
			findPath(now, district);
		}
		if (district == 2)
		{
			now.x -= 1;
			findPath(now, district);
		}
		if (district == 3)
		{
			now.y -= 1;
			findPath(now, district);
		}
		if (district == 4)
		{
			now.x += 1;
			findPath(now, district);
		}
	}

	if (map[now.y][now.x] > 0 && map[now.y][now.x] < 5)
	{
		node new1 = now;
		node new2 = now;

		if (district == 1)
		{
			new1.x += 1;
			new2.x -= 1;
			findPath(new1, 4);
			findPath(new2, 2);
		}
		if (district == 2)
		{
			new1.y += 1;
			new2.y -= 1;
			findPath(new1, 1);
			findPath(new2, 3);
		}
		if (district == 3)
		{
			new1.x += 1;
			new2.x -= 1;
			findPath(new1, 4);
			findPath(new2, 2);
		}
		if (district == 4)
		{
			new1.y += 1;
			new2.y -= 1;
			findPath(new1, 1);
			findPath(new2, 3);
		}
	}

	book[now.y][now.x] = 0;

	while (!output_stack.empty()) {
		output_stack.pop();
	}
}

void main() {
	start.x = 0, start.y = 0;
	target.x = 3, target.y = 4;
	findPath(start, 1);
	if (!flag)
	{
		cout << "没有路" << endl;
	}
}

思想

对于这种找到路径的问题，我们第一想法就是广搜和深搜。那么这个游戏的方法，我们可以从入水口判断出下一个水管是什么样的，所以用广搜的话，会多出一些没有用的判断，浪费一些时间，虽然对于电脑来说没有多大的影响，而且这种游戏也不会将地图设置多大，但是能用深搜何必用广搜呢。

然后首先考虑递归需要迭代的参数，首先这种地图肯定坐标是要递归的，其次我们需要上一次的接水管的方向，这样递归就有一个问题，就是最后的水管要匹配两个方向，一个是入水口，一个是出水口。我们可以将最后的水管外面那个当成一个水管，那么最后一个就不用特殊处理了，但是如果把地图外的当成水管，那么判断超界又有问题了，所以必须把赢得判断放在超界的判断上面。