【※ LeetCode 劍指 Offer 12. 矩陣中的路徑(簡單)】

題目：

給定一個 m x n 二維字符網格 board 和一個字符串單詞 word 。如果 word 存在於網格中，返回 true ；否則，返回 false 。

單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重複使用。

例如，在下面的 3×4 的矩陣中包含單詞 “ABCCED”（單詞中的字母已標出）。

示例 1：

輸入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
輸出：true
示例 2：

輸入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
輸出：false

提示：

1 <= board.length <= 200
1 <= board[i].length <= 200
board 和 word 僅由大小寫英文字母組成

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解題過程：

思路來自LeetCode用戶：Carol

dfs + 回溯；
使用二維布爾數組記錄之前的比特置是否已經被訪問過，如果已經被訪問過的話，則在 dfs 的過程中，直接 return false 即可。也就是說，此路已經不通了；
如果當前遍曆到的字符不等於 board[i][j] 比特置上的字符，那麼說明此路也是不通的，因此返回 false；
至於遞歸結束的條件：如果指針 start 能够來到 word 的最後一個字符，那麼說明能够在矩陣 board 中找到一條路徑，此時返回 true；
在遍曆到當前 board[i][j] 的時候，首先應將該比特置的 visited[i][j] 設置為 true，錶明訪問過；
然後，遞歸地去 board[i][j] 的上下左右四個方向去找，剩下的路徑；
在 dfs 的過程當中，如果某條路已經不通了，那麼那麼需要回溯，也就是將 visited[i][j] 比特置的布爾值重新賦值為 fasle；
最後，返回 ans 即可。

class Solution {
    
    public boolean exist(char[][] board, String word) {
    
        if (board == null || board.length == 0 || board[0].length == 0) {
    
            return false;
        }

        char[] chars = word.toCharArray();
        boolean[][] visited = new boolean[board.length][board[0].length];
        
        for(int i=0; i<board.length; i++){
    
            for(int j=0; j<board[0].length;j++){
    
                // 從（0,0）開始進行dfs操作，不斷地去找。
                // 如果以（0,0）點沒有對應的路徑的話，那麼就從（0,1）點開始去找
                if(dfs(board, chars, visited, i, j, 0)){
    
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] chars, boolean[][] visited,int i,int j,int start){
    
        if(i<0 || i>=board.length || j<0 || j>=board[0].length
            || chars[start]!=board[i][j] || visited[i][j]){
    
                return false;
            }
        
        if(start == chars.length-1){
    
            return true;
        }

        visited[i][j] = true;
        boolean ans = false;
        ans = dfs(board, chars, visited, i+1, j, start+1)   // 向右
            || dfs(board, chars, visited, i-1, j, start+1)  // 向左
            || dfs(board, chars, visited, i, j+1, start+1)  // 向下
            || dfs(board, chars, visited, i, j-1, start+1);  // 向上
        
        visited[i][j] = false;
        return ans;
    }
}

執行結果：

學習了！