啊哈算法之水管工游戏

简述

本算法摘选自啊哈磊所著的《啊哈！算法》第四章第六节的题目——水管工游戏。文中代码使用c语言编写，博主通过阅读和理解，重新由java代码实现了一遍。

游戏介绍

游戏内容介绍在原文中表述详细，并附带了图片加以说明，同时给出了解答思路，这里有点需要说明的是，原文中作者为了方便读者理解，特地将开始位置设置为了(1, 1)，而在我用java改写之后，就恢复到了数组中以原点(0, 0)来表示了，不冲突，只是在阅读原文思路分析和博主代码对比时需要注意这一点差异。因为原文篇幅较大，而且说明的内容较为丰富，在此就直接引荐原文内容了。

 

（以上图片来源于原文截图）

代码实现

更多关于上文分析内容，均可以在以下的代码实现的注释中得到答案。

  1 /**
  2  * @project: dailypro
  3  * @packagename: com.captainad.algorithm
  4  * @author: captain&d
  5  * @website: https://www.cnblogs.com/captainad/
  6  * @datetime: 2019/6/21 12:00.
  7  * @description: 水管工游戏
  8  */
  9 public class plumbergame {
 10 
 11     /**
 12      * 自定义内部类，代表管道所处节点
 13      */
 14     static class plumbernode {
 15         /** 横坐标 */
 16         int x;
 17 
 18         /** 纵坐标 */
 19         int y;
 20 
 21         public plumbernode(int x, int y) {
 22             this.x = x;
 23             this.y = y;
 24         }
 25     }
 26 
 27     /**
 28      * 自定义内部类，表示栈，用来记录铺设管道的路径
 29      */
 30     static class plumberstack {
 31         /** 数据栈 */
 32         plumbernode[] data = new plumbernode[100];
 33 
 34         /** 栈顶指针，初始值为0 */
 35         int top = 0;
 36     }
 37 
 38     /** 二维数组模拟水管铺设地图 */
 39     private static int[][] map = new int[10][10];
 40 
 41     /** 桶，标记已经铺设过的点位 */
 42     private static int[][] book = new int[10][10];
 43 
 44     /** 地图边界，以及是否到达重点的标记 */
 45     private static int m = 0, n = 0, flag = 0;
 46 
 47     /**
 48      * 递归处理每一个单元格位置所能处理的管道摆放方式
 49      * @param x 单元格横坐标
 50      * @param y 单元格纵坐标
 51      * @param front 当前单元格中进水口方向
 52      * @param stack 表示铺设管道记录铺设路径的栈
 53      */
 54     public static void dfs(int x, int y, int front, plumberstack stack) {
 55 
 56         // 判断是否以及到达终点位置，其中xy都是从0开始计算。
 57         // 这里因为最后的出水口在地图外面，所以如果到达最后地图外的那个点位，则说明管道铺设完成
 58         if(x == (m - 1) && y == n) {
 59 
 60             // 更新完成管道的铺设标记
 61             flag = 1;
 62 
 63             // 找到铺设方案，打印铺设轨迹
 64             for(int i = 0; i < stack.top; i++) {
 65                 system.out.print(string.format("(%d, %d) ", stack.data[i].x + 1, stack.data[i].y + 1));
 66             }
 67 
 68             // 到此返回
 69             return;
 70         }
 71 
 72         // 判断是否越界，注意如果有上面这层判断，越界判断就得放在下面
 73         if(x < 0 || x >= m || y < 0 || y >= n) {
 74             return;
 75         }
 76 
 77         // 判断当前点位管道是否已经使用过，使用过则掠过，没有使用则继续并加入到桶中标记
 78         if(book[x][y] == 1) {
 79             return;
 80         }
 81         book[x][y] = 1;
 82 
 83         // 将当前尝试的坐标入栈，然后栈顶指针上移一位
 84         plumbernode node = new plumbernode(x, y);
 85         stack.data[stack.top] = node;
 86         stack.top++;
 87 
 88         // 当当前管道是直管的情况
 89         if(map[x][y] >= 5 && map[x][y] <= 6) {
 90 
 91             // 进水口在左边的情况
 92             if(front == 1) {
 93                 // 此时只能使用5号这种摆放方式，且下次进水口也是在左边
 94                 dfs(x, y+1, 1, stack);
 95             }
 96 
 97             // 进水口在上边的情况
 98             if(front == 2) {
 99                 // 此时只能使用6号这种摆放方式，且下次进水口也是在上边
100                 dfs(x+1, y, 2, stack);
101             }
102 
103             // 进水口在右边的情况
104             if(front == 3) {
105                 // 此时只能使用5号这种摆放方式，且下次进水口也是在右边
106                 dfs(x, y - 1, 3, stack);
107             }
108 
109             // 进水口在下边的情况
110             if(front == 4) {
111                 // 此时只能使用6号这种摆放方式，且下次进水口也是在下边
112                 dfs(x - 1, y, 4, stack);
113             }
114 
115         }
116 
117         // 当当前管道是弯管时
118         if(map[x][y] >= 1 && map[x][y] <= 4) {
119 
120             // 进水口在左边的情况
121             if(front == 1) {
122 
123                 // 此时可以有3，4号两种摆放方式
124                 // 下一次的进水口就有可能是在上边或者在下边了，这取决于用哪一种摆放方式
125                 dfs(x + 1, y, 2, stack);
126                 dfs(x - 1, y, 4, stack);
127             }
128 
129             // 进水口在上边的情况
130             if(front == 2) {
131 
132                 // 此时可以有1，4号两种摆放方式
133                 dfs(x, y + 1, 1, stack);
134                 dfs(x, y - 1, 3, stack);
135             }
136 
137             // 进水口在右边的情况
138             if(front == 3) {
139 
140                 // 此时可以有1，2号两种摆放方式
141                 dfs(x - 1, y, 4, stack);
142                 dfs(x + 1, y, 2, stack);
143             }
144 
145             // 进水口在下边的情况
146             if(front == 4) {
147 
148                 // 此时可以有2，3号两种摆放方式
149                 dfs(x, y + 1, 1, stack);
150                 dfs(x, y - 1, 3, stack);
151             }
152 
153         }
154 
155         // 尝试完这种方式，如果不行则需要回退重新尝试，取消桶标记，同时栈中记录的点位出栈
156         book[x][y] = 0;
157         stack.top --;
158         return;
159     }
160 
161     public static void main(string[] args) {
162         // 铺设管道开始的点位，同时第一个进水方先是1
163         int startx = 0, starty = 0, front = 1;
164 
165         // 设定游戏地图边界
166         m = 5;
167         n = 4;
168 
169         // 初始化游戏地图
170         map[0][0] = 5;
171         map[0][1] = 3;
172         map[0][2] = 5;
173         map[0][3] = 3;
174         map[1][0] = 1;
175         map[1][1] = 5;
176         map[1][2] = 3;
177         map[1][3] = 0;
178         map[2][0] = 2;
179         map[2][1] = 3;
180         map[2][2] = 5;
181         map[2][3] = 1;
182         map[3][0] = 6;
183         map[3][1] = 1;
184         map[3][2] = 1;
185         map[3][3] = 5;
186         map[4][0] = 1;
187         map[4][1] = 5;
188         map[4][2] = 5;
189 
190         map[4][3] = 4;
191 
192         // 初始化记录管道铺设路径的栈
193         plumberstack stack = new plumberstack();
194 
195         // 开始游戏
196         dfs(startx, starty, front, stack);
197 
198         if(flag == 0) {
199             system.out.println("impossible!");
200         }else {
201             system.out.println("\nyes, we did it.");
202         }
203     }
204 }

参考资料

1、《啊哈！算法》/ 啊哈磊著. 人民邮电出版社