1
【面试现场】如何编程解决华容道问题？
source link: https://www.cxyxiaowu.com/5653.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
【面试现场】如何编程解决华容道问题？
小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT互联网公司。
今天他就去一家外企面试了。
【面试前】
面试前，小史就收到了中英文的面试邀请。
去外企面试，最好要能够和面试官英语对话。小史除了复习算法之外，赶紧练起了口语。
【五分钟学算法面试现场】
面试官给了小史一个问题。（题目已翻译成中文，请自行脑补英文现场）
题目：我有1到8八个数字，放在一个3×3的九宫格里面，那么会留下一个空格。
空格可以和上下左右的数字进行交换，你可以认为空格在移动。如果移动成
则游戏胜利。
你需要完成以下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<Integer> moveArr = new LinkedList<Integer>();
// 初始化，数字0代表空格，先遍历，找出空格的位置
public HuaRongDao(int[][] arr) {
this.arr = arr;
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
if(arr[i][j] == 0) {
x = i;
y = j;
}
}
}
}
// 判断是否可以朝某个方向进行移动
public boolean canMove(int direction) {
switch (direction) {
// y > 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<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
System.out.print(arr[i][j]);
System.out.print(" ");
}
System.out.println();
}
}
}
【请教大神】
小史回到学校，把面试的情况和计算机学院的吕老师说了一下。
【迷宫问题】
小史：每个点都可以按照右下左上的方向来进行尝试，如果是墙壁，就换一个方向，如果可以走，就往前走到下一点，然后再接着尝试。直到到达终点为止。
吕老师随手又画了一个迷宫。
吕老师：小史，这块并不是往左走，而是回退，退回到上一步。如果我们正在往前搜索，当然不能走回头路。但是当前面没有路的时候，我们就需要返回来，找到之前有可能出现岔路口的地方，再去下一个方向进行搜索。
【华容道问题】
小史：吕老师，我明白了，空格在华容道中移动，就好像我在迷宫里走动一样，每次到一个新的状态，就有几个方向可以搜索，如果是之前碰到过的状态，那就不搜索。
【递归实现回溯】
小史：“回溯”的过程有点像栈的操作。往前走一步就像是入栈，到了死胡同，要往回退，就像是出栈。
吕老师：这个过程确实是栈的过程，但是直接用栈的话，对于你刚刚接触搜索算法，可能编码比较难。其实你可以用递归来实现这个搜索过程。
小史：我在走迷宫的时候，每走一步，就把这一步是往哪走的记录下来，但是碰到了死胡同，往回退的时候，我又把之前记录的步骤最后一步去掉。这样一来，达到终点的时候，我记下来的步骤就是一条从起点到终点的路径了。
小史：记录移动路径，其实就是在真正搜索之前，把方向记录下来，而搜索如果要返回了，则说明该次搜索已经结束，没有结果，应该把该记录去除。
【小史的努力】
吃完烤串，喝完小酒，小史和吕老师休闲地走在回学校的路上。
吕老师笑而不语。
回到宿舍，小史就打开了电脑，手在键盘上飞快地敲了起来。
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
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<Integer> moveArr = new LinkedList<Integer>();
// 定义终点状态
private static final Integer WIN_STATE = 123456780;
// 保存已经搜索过的状态
private Set<Integer> statusSet = new HashSet<Integer>();
// 初始化，数字0代表空格，先遍历，找出空格的位置
public HuaRongDao(int[][] arr) {
this.arr = arr;
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
if(arr[i][j] == 0) {
x = i;
y = j;
}
}
}
}
// 判断是否可以朝某个方向进行移动
private boolean canMove(int direction) {
switch (direction) {
// y > 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<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
status = status * 10 + arr[i][j];
}
}
return status;
}
// 搜索方法
private boolean search(int direction) {
// 如果能够朝该方向行走
if(canMove(direction)) {
// 往该方向移动
move(direction);
// 移动后的状态
Integer status = getStatus();
// 如果已经是胜利状态，返回true
if(WIN_STATE.equals(status)) {
return true;
}
// 如果是之前走过的状态了，返回false
if(statusSet.contains(status)) {
// 这一步走错了，回退
moveBack(direction);
return false;
}
// 将当前状态存入set
statusSet.add(status);
// 继续朝四个方向进行搜索
boolean searchFourOk = search(RIGHT) || search(DOWN) || search(LEFT) || search(UP);
if(searchFourOk) {
return true;
} else {
// 这一步走错了，把它的记录去除
moveBack(direction);
return false;
}
}
return false;
}
// 解题入口方法
public boolean solve() {
Integer status = getStatus();
// 如果已经是胜利状态，返回true
if(WIN_STATE.equals(status)) {
return true;
}
// 初始状态先记录
statusSet.add(status);
// 朝4个方向进行搜索
return search(RIGHT) || search(DOWN) || search(LEFT) || search(UP);
}
// 打印路径
public void printRoute() {
for(int i=0; i<moveArr.size(); i++) {
System.out.print(getDirString(moveArr.get(i)));
System.out.print(" ");
}
}
// 方向与其对应的字符串
private String getDirString(int dir) {
switch (dir) {
case LEFT:
return "左";
case RIGHT:
return "右";
case UP:
return "上";
case DOWN:
return "下";
}
return null;
}
// 打印当前华容道的状态
public void print() {
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
System.out.print(arr[i][j]);
System.out.print(" ");
}
System.out.println();
}
}
}
几个测试用例下来，小史眉头一皱，发现事情并不简单。
小史经过缜密的分析，找到了原因。
我可以判断一下，如果某条路走的步数超过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<Integer> moveArr = new LinkedList<Integer>();
// 定义终点状态
private static final Integer WIN_STATE = 123456780;
// 保存已经搜索过的状态
private Set<Integer> statusSet = new HashSet<Integer>();
// 代表广搜的每一步，通过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<SearchItem> statusToSearch = new LinkedList<SearchItem>();
// 初始化，数字0代表空格，先遍历，找出空格的位置
public HuaRongDao(int[][] arr) {
this.arr = arr;
getXY();
}
// 获取空格的x和y坐标
private void getXY() {
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
if(arr[i][j] == 0) {
x = i;
y = j;
}
}
}
}
// 判断是否可以朝某个方向进行移动
private boolean canMove(int direction) {
switch (direction) {
// y > 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<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
status = status * 10 + arr[i][j];
}
}
return status;
}
// 根据状态还原九宫格数组
// 该方法是getStatus的逆过程
public void recoverStatus(Integer status) {
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
arr[2 - i][2 - j] = status % 10;
status = status / 10;
}
}
getXY();
}
// 搜索方法
private boolean search() {
// 如果还有要搜索的状态
while(statusToSearch.size() > 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<moveArr.size(); i++) {
System.out.print(getDirString(moveArr.get(i)));
System.out.print(" ");
}
}
// 方向与其对应的字符串
private String getDirString(int dir) {
switch (dir) {
case LEFT:
return "左";
case RIGHT:
return "右";
case UP:
return "上";
case DOWN:
return "下";
}
return null;
}
// 打印当前华容道的状态
public void print() {
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr.length; j++) {
System.out.print(arr[i][j]);
System.out.print(" ");
}
System.out.println();
}
}
}
写完代码，小史赶紧运行看下最终结果：
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
一个问题一顿饭，吕老师不亏的。
【饭桌上的闲聊】
PS：这次这篇花费了两周时间以及小史两顿饭钱。如果你看到了这里，并且有所收获的话，可以动动手指转发一下哦，小史和吕老师都会感谢你。
五分钟学算法面试现场是互联网侦察推出的一个新的板块，旨在回放真实的面试过程，并对面试题进行全面解析，提供多种思路，比较优劣，希望对大家的面试有所帮助。
【五分钟学算法面试现场】如何判断一个数是否在40亿个整数中？
原文始发于微信公众号（互联网侦察）：【五分钟学算法面试现场】如何编程解决华容道问题？
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK