点击上方“程序人生”，选择“置顶公众号”

第一时间关注程序猿（媛）身边的故事

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

作者

 channingbreeze

已获原作者授权，如需转载，请联系原作者。

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

【面试前】

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

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

【面试现场】

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

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

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

则游戏胜利。

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

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

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

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

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

【请教大神】

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

【迷宫问题】

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

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

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

【华容道问题】

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

【递归实现回溯】

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

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

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

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

【小史的努力】

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

吕老师笑而不语。

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

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

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

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

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

小史在search函数中增加了moveArr.size(){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                if(arr[i][j] == 0) {                    x = i;                    y = j;                }            }        }    }    // 判断是否可以朝某个方向进行移动    private boolean canMove(int direction) {        switch (direction) {            // y > 0才能左移            case LEFT:                return y > 0;            // y  0;            // x             // y > 0才能左移            case LEFT:                return RIGHT;            // y  0才能上移            case UP:                return DOWN;            // x         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                status = status * 10 + arr[i][j];            }        }        return status;    }    // 根据状态还原九宫格数组    // 该方法是getStatus的逆过程    public void recoverStatus(Integer status) {        for(int i=0; i                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                    // 向前一步                    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        switch (dir) {            case LEFT:                return "左";            case RIGHT:                return "右";            case UP:                return "上";            case DOWN:                return "下";        }        return null;    }    // 打印当前华容道的状态    public void print() {        for(int i=0; i                System.out.print(arr[i][j]);                System.out.print(" ");            }            System.out.println();        }    }}

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

一个问题一顿饭，吕老师不亏的。

【饭桌上的闲聊】

PS：这次这篇花费了两周时间以及小史两顿饭钱。如果你看到了这里，并且有所收获的话，可以动动手指转发一下哦，小史和吕老师都会感谢你。

- The End -

「若你有原创文章想与大家分享，欢迎投稿。」

加编辑微信ID，备注#投稿#：

程序 丨 druidlost  

小七 丨 duoshangshuang

程序人生地区交流群，了解一下

根据你所在的城市，回复相应关键词“北京”，“沪杭”或“广东”，我会拉你进相应地区群哦~（目前只有该三个地区群）

（注意：进你所在城市或者最希望进的地区群，以上3个地区群不必重复进入，谢谢配合。）

上期精彩内容