如何通過程式設計解決華容道問題?
點選上方“ 程式人生 ”,選擇“置頂公眾號”
第一時間關注程式猿(媛)身邊的故事
小史是一個應屆生,雖然學的是電子專業,但是自己業餘時間看了很多網際網路與程式設計方面的書,一心想進 BAT 網際網路公司。
作者
channingbreeze
已獲原作者授權,如需轉載,請聯絡原作者。
今天他就去一家外企面試了。
【面試前】
面試前,小史就收到了中英文的面試邀請。
去外企面試,最好要能夠和麵試官英語對話。小史除了複習演算法之外,趕緊練起了口語。
【面試現場】
面試官給了小史一個問題。(題目已翻譯成中文,請自行腦補英文現場)
題目:我 有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}, {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:這次這篇花費了兩週時間以及小史兩頓飯錢。如果你看到了這裡,並且有所收穫的話,可以動動手指轉發一下哦,小史和呂老師都會感謝你。
- The End -
「若你有原創文章想與大家分享,歡迎投稿。」
加編輯微信ID,備註#投稿#:
程式 丨 druidlost
小七 丨 duoshangshuang
程式人生地區交流群,瞭解一下
根據你所在的城市,回覆相應關鍵詞“北京”,“滬杭”或“廣東”,我會拉你進相應地區群哦~(目前只有該三個地區群)
(注意:進你所在城市或者最希望進的地區群,以上3個地區群不必重複進入,謝謝配合。)
上期精彩內容