Leetcode 79. 单词搜索（迷宫回溯）

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

---

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

---

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
输出：true

---

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB”
输出：false

---

【思路】
常规的迷宫回溯搜索问题。

回溯时只需要注意几个点：
1、每次试探是否在矩阵范围内，不能超出地图范围
2、是否能够保证“不走回头路”。需要用vis数组标记走过的点。
3、迷宫的起点取决于word字符串的首字符。
4、想好递归的终止条件，即正好是word的最后一个字符且与迷宫上对应的字符相等。

---

【代码】：

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */

//k表示当前是wordArr里的第几个
var dfs = function(x, y,board, wordArr, k, vis){
    var m = board.length;
    var n = board[0].length;
    if(x >= m || y >= n || x < 0 || n < 0)    return false;
    if(vis[x][y] == 1)  return false;
    if(board[x][y] != wordArr[k])   return false;
    if(board[x][y] == wordArr[k] && k == wordArr.length - 1)    return true;
    // 四个方向搜索
    var isfind = false;
    //走迷宫不要忽略这一步，要确保不走回头路
    vis[x][y] = 1;
    isfind = dfs(x + 1, y, board, wordArr, k + 1, vis) || dfs(x - 1, y, board, wordArr, k + 1, vis) || dfs(x, y + 1, board, wordArr, k + 1, vis) || dfs(x, y - 1, board, wordArr, k + 1, vis);
    vis[x][y] = 0;
    return isfind;
}

var exist = function(board, word) {
    var wordArr = word.split("");
    var first = wordArr[0];
    var m = board.length;
    var n = board[0].length;
    var isfind = false;
    var vis = Array(m).fill().map(() => Array(n).fill(0));
    console.log(vis) 
    for(let i = 0;i < m && !isfind;i++){
        for(let j = 0;j < n && !isfind;j++){
            if(board[i][j] == first){
                isfind = dfs(i, j, board, wordArr, 0, vis);
            }
        }
    }
    return isfind;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40