查看原文
其他

【面试现场】如何编程解决华容道问题?

channingbreeze 互联网侦察 2018-11-24


小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进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<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}, {01}, {-10}, {10}};

    // 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, nullnull));
        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亿个整数中?



    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存