欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

啊哈算法之水管工游戏

程序员文章站 2023-08-12 10:13:36
简述 本算法摘选自啊哈磊所著的《啊哈!算法》第四章第六节的题目——水管工游戏。文中代码使用C语言编写,博主通过阅读和理解,重新由Java代码实现了一遍。 游戏介绍 游戏内容介绍在原文中表述详细,并附带了图片加以说明,同时给出了解答思路,这里有点需要说明的是,原文中作者为了方便读者理解,特地将开始位置 ......

简述

本算法摘选自啊哈磊所著的《啊哈!算法》第四章第六节的题目——水管工游戏。文中代码使用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、《啊哈!算法》/ 啊哈磊著. 人民邮电出版社