「面试现场」如何编程解决华容道问题？

来源：互联网侦察

小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT互联网公司。

今天他就去一家外企面试了。

【面试前】

面试前，小史就收到了中英文的面试邀请。

去外企面试，最好要能够和面试官英语对话。小史除了复习算法之外，赶紧练起了口语。

【面试现场】

面试官给了小史一个问题。（题目已翻译成中文，请自行脑补英文现场）

题目：我有1到8八个数字，放在一个3x3的九宫格里面，那么会留下一个空格。

空格可以和上下左右的数字进行交换，你可以认为空格在移动。如果移动成

则游戏胜利。

你需要完成以下2件事情：

1、给出数据结构来描述这个过程。

2、给你一个初始状态，告诉我能不能胜利，并给出如何移动才能胜利。

这有点像咱们中国的华容道游戏。

小史把他能想到的都写了下来。

import java.util.LinkedList;import java.util.List;/** * @author xiaoshi on 2018/9/8. */public class HuaRongDao { // 定义方向 public static final int LEFT = 1; public static final int RIGHT = 2; public static final int UP = 3; public static final int DOWN = 4; // 3x3的九宫格 private int[][] arr; // 记录空格的位置 private int x; private int y; // 定义移动的数组 private List moveArr = new LinkedList(); // 初始化，数字0代表空格，先遍历，找出空格的位置 public HuaRongDao(int[][] arr) { this.arr = arr; for(int i=0; i 0才能左移 case LEFT: return y > 0; // y < 2才能右移 case RIGHT: return y < 2; // x > 0才能上移 case UP: return x > 0; // x < 2才能下移 case DOWN: return x < 2; } return false; } // 朝某个方向进行移动，该函数不作判断，直接移动 // 调用前请自行用canMove先行判断 public void move(int direction) { int temp; switch (direction) { // 空格和左侧数字交换 case LEFT: temp = arr[x][y - 1]; arr[x][y - 1] = 0; arr[x][y] = temp; y = y - 1; break; // 空格和右侧数字交换 case RIGHT: temp = arr[x][y + 1]; arr[x][y + 1] = 0; arr[x][y] = temp; y = y + 1; break; // 空格和上方数字交换 case UP: temp = arr[x - 1][y]; arr[x - 1][y] = 0; arr[x][y] = temp; x = x - 1; break; // 空格和下方数字交换 case DOWN: temp = arr[x + 1][y]; arr[x + 1][y] = 0; arr[x][y] = temp; x = x + 1; break; } } // 打印当前华容道的状态 public void print() { for(int i=0; i

【请教大神】

小史回到学校，把面试的情况和计算机学院的吕老师说了一下。

【迷宫问题】

小史：每个点都可以按照右下左上的方向来进行尝试，如果是墙壁，就换一个方向，如果可以走，就往前走到下一点，然后再接着尝试。直到到达终点为止。

吕老师随手又画了一个迷宫。

吕老师：小史，这块并不是往左走，而是回退，退回到上一步。如果我们正在往前搜索，当然不能走回头路。但是当前面没有路的时候，我们就需要返回来，找到之前有可能出现岔路口的地方，再去下一个方向进行搜索。

【华容道问题】

小史：吕老师，我明白了，空格在华容道中移动，就好像我在迷宫里走动一样，每次到一个新的状态，就有几个方向可以搜索，如果是之前碰到过的状态，那就不搜索。

【递归实现回溯】

小史：“回溯”的过程有点像栈的操作。往前走一步就像是入栈，到了死胡同，要往回退，就像是出栈。

吕老师：这个过程确实是栈的过程，但是直接用栈的话，对于你刚刚接触搜索算法，可能编码比较难。其实你可以用递归来实现这个搜索过程。

小史：我在走迷宫的时候，每走一步，就把这一步是往哪走的记录下来，但是碰到了死胡同，往回退的时候，我又把之前记录的步骤最后一步去掉。这样一来，达到终点的时候，我记下来的步骤就是一条从起点到终点的路径了。

小史：记录移动路径，其实就是在真正搜索之前，把方向记录下来，而搜索如果要返回了，则说明该次搜索已经结束，没有结果，应该把该记录去除。

【小史的努力】

吃完烤串，喝完小酒，小史和吕老师休闲地走在回学校的路上。

吕老师笑而不语。

回到宿舍，小史就打开了电脑，手在键盘上飞快地敲了起来。

理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：

import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.Set;/** * @author xiaoshi on 2018/9/8. */public class HuaRongDao { // 定义方向 private static final int LEFT = 1; private static final int RIGHT = 2; private static final int UP = 3; private static final int DOWN = 4; // 3x3的九宫格 private int[][] arr; // 记录空格的位置 private int x; private int y; // 定义移动的数组 private List moveArr = new LinkedList(); // 定义终点状态 private static final Integer WIN_STATE = 123456780; // 保存已经搜索过的状态 private Set statusSet = new HashSet(); // 初始化，数字0代表空格，先遍历，找出空格的位置 public HuaRongDao(int[][] arr) { this.arr = arr; for(int i=0; i 0才能左移 case LEFT: return y > 0; // y < 2才能右移 case RIGHT: return y < 2; // x > 0才能上移 case UP: return x > 0; // x < 2才能下移 case DOWN: return x < 2; } return false; } // 朝某个方向进行移动，该函数不作判断，直接移动 // 调用前请自行用canMove先行判断 private void move(int direction) { int temp; switch (direction) { // 空格和左侧数字交换 case LEFT: temp = arr[x][y - 1]; arr[x][y - 1] = 0; arr[x][y] = temp; y = y - 1; break; // 空格和右侧数字交换 case RIGHT: temp = arr[x][y + 1]; arr[x][y + 1] = 0; arr[x][y] = temp; y = y + 1; break; // 空格和上方数字交换 case UP: temp = arr[x - 1][y]; arr[x - 1][y] = 0; arr[x][y] = temp; x = x - 1; break; // 空格和下方数字交换 case DOWN: temp = arr[x + 1][y]; arr[x + 1][y] = 0; arr[x][y] = temp; x = x + 1; break; } // 该方向记录 moveArr.add(direction); } // 某个方向的回退，该函数不作判断，直接移动 // 其操作和move方法正好相反 private void moveBack(int direction) { int temp; switch (direction) { // 空格和左侧数字交换 case LEFT: temp = arr[x][y + 1]; arr[x][y + 1] = 0; arr[x][y] = temp; y = y + 1; break; // 空格和右侧数字交换 case RIGHT: temp = arr[x][y - 1]; arr[x][y - 1] = 0; arr[x][y] = temp; y = y - 1; break; // 空格和上方数字交换 case UP: temp = arr[x + 1][y]; arr[x + 1][y] = 0; arr[x][y] = temp; x = x + 1; break; // 空格和下方数字交换 case DOWN: temp = arr[x - 1][y]; arr[x - 1][y] = 0; arr[x][y] = temp; x = x - 1; break; } // 记录的移动步骤出栈 moveArr.remove(moveArr.size() - 1); } // 获取状态，这里把9个数字按顺序组成一个整数来代表状态 // 方法不唯一，只要能区分九宫格状态就行 private Integer getStatus() { int status = 0; for(int i=0; i

几个测试用例下来，小史眉头一皱，发现事情并不简单。

小史经过缜密的分析，找到了原因。

我可以判断一下，如果某条路走的步数超过100步，就不再走了，赶紧回退。

小史在search函数中增加了moveArr.size()<100的判断，得到了最终结果。

【深搜和广搜】

第二天，小史得意洋洋地拿着自己的代码去找吕老师秀起来。

小史：现在的算法，没办法保证得到的解法就是最优解，并且它很容易进入复杂的死胡同出不来，有点像一个死钻牛角尖的人。

吕老师：深度优先搜索，会在一个方向一直搜下去，直到这条路走不通，才会考虑第二个方向。

吕老师：广度优先搜索，是先搜索每一个可行方向的第一步，然后再接着搜索每一个可行方向的第二步。以此类推。

小史：这个算法似乎没有“回溯”的必要了，没办法再用递归了吧？而且分头搜索这个方式应该怎么实现呢？

吕老师：你可以将要搜索的初始状态加到一个队列里，然后每次从队列中取出一个状态，往可以前进的方向前进一步，然后再将该状态放到队列。利用队列先进先出的特点，就可以实现广搜的效果。

小史：每一步都记录上一步的状态和这次的方向。这样在达到最终胜利状态的时候，可以找到这个状态的上一步。而上一步又可以找到上上步，这不就是链表么？

理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：

import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.Set;/** * @author xiaoshi on 2018/9/9. */public class HuaRongDao { // 定义方向 private static final int LEFT = 0; private static final int RIGHT = 1; private static final int UP = 2; private static final int DOWN = 3; // 定义辅助数组 private static final int[][] dxdy = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 3x3的九宫格 private int[][] arr; // 记录空格的位置 private int x; private int y; // 定义移动的数组 private List moveArr = new LinkedList(); // 定义终点状态 private static final Integer WIN_STATE = 123456780; // 保存已经搜索过的状态 private Set statusSet = new HashSet(); // 代表广搜的每一步，通过lastItem链起来 private class SearchItem { private Integer status; private Integer dir; private SearchItem lastItem; SearchItem(Integer status, Integer dir, SearchItem lastItem) { this.status = status; this.dir = dir; this.lastItem = lastItem; } public Integer getStatus() {return status;} public Integer getDir() {return dir;} public SearchItem getLastItem() {return lastItem;} } // 广搜的存储队列 private List statusToSearch = new LinkedList(); // 初始化，数字0代表空格，先遍历，找出空格的位置 public HuaRongDao(int[][] arr) { this.arr = arr; getXY(); } // 获取空格的x和y坐标 private void getXY() { for(int i=0; i 0才能左移 case LEFT: return y > 0; // y < 2才能右移 case RIGHT: return y < 2; // x > 0才能上移 case UP: return x > 0; // x < 2才能下移 case DOWN: return x < 2; } return false; } // 找出该方向的相反方向 private int getBackDir(int direction) { switch (direction) { // y > 0才能左移 case LEFT: return RIGHT; // y < 2才能右移 case RIGHT: return LEFT; // x > 0才能上移 case UP: return DOWN; // x < 2才能下移 case DOWN: return UP; } return 0; } // 朝某个方向进行移动，该函数不作判断，直接移动 // 调用前请自行用canMove先行判断 private void move(int direction) { int temp; temp = arr[x + dxdy[direction][0]][y + dxdy[direction][1]]; arr[x + dxdy[direction][0]][y + dxdy[direction][1]] = 0; arr[x][y] = temp; x = x + dxdy[direction][0]; y = y + dxdy[direction][1]; } // 某个方向的前进，该函数不作判断，直接移动 private void moveForward(int direction) { move(direction); // 该方向记录 moveArr.add(direction); } // 某个方向的回退，该函数不作判断，直接移动 // 其操作和moveForward方法正好相反 private void moveBack(int direction) { move(getBackDir(direction)); // 记录的移动步骤出栈 moveArr.remove(moveArr.size() - 1); } // 获取状态，这里把9个数字按顺序组成一个整数来代表状态 // 方法不唯一，只要能区分九宫格状态就行 public Integer getStatus() { int status = 0; for(int i=0; i 0) { // 队首出列 SearchItem item = statusToSearch.remove(0); Integer status = item.getStatus(); // 搜到了 if(status.equals(WIN_STATE)) { // 找到路径 recordRoute(item); return true; } // 根据status还原arr和x，y recoverStatus(status); // 4个方向进行遍历 for(int i=0; i<4; i++) { // 如果能够朝该方向行走 if(canMove(i)) { // 向前一步 moveForward(i); status = getStatus(); // 之前搜过的状态 if (statusSet.contains(status)) { moveBack(i); // 放弃 continue; } // 新状态加入待搜索 statusSet.add(status); statusToSearch.add(new SearchItem(status, i, item)); moveBack(i); } } } return false; } // 解题入口方法 public boolean solve() { Integer status = getStatus(); // 如果已经是胜利状态，返回true if(WIN_STATE.equals(status)) { return true; } // 初始状态先记录 statusSet.add(status); // 初始状态进入搜索队列 statusToSearch.add(new SearchItem(status, null, null)); return search(); } // 根据链表顺藤摸瓜，找到路径 private void recordRoute(SearchItem item) { while(null != item.getLastItem()) { moveArr.add(0, item.getDir()); item = item.getLastItem(); } } // 打印路径 public void printRoute() { for(int i=0; i

写完代码，小史赶紧运行看下最终结果：

1 2 3 4 5 6 8 7 0 无法胜利1 2 3 4 0 6 7 5 8 可以胜利，路径为：下右 3 4 1 5 6 0 8 2 7 可以胜利，路径为：左左上右下左下右右上左左下右上上右下左左上右下右下 Process finished with exit code 0