79.word-search.md

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/word-search
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

dfs & 递归 & 回溯 & 剪枝

func exist(board [][]byte, word string) bool {
	if len(board) == 0 || len(board[0]) == 0 {
		return false
	}
	for m := 0; m < len(board); m++ {
		for n := 0; n < len(board[0]); n++ {
			if (dfs(board, m, n, word, 0)) {
				return true
			}
		}
	}
	return false
}

var dirM = []int{-1, 0, 1, 0}
var dirN = []int{0, 1, 0, -1}

func dfs(board [][]byte, m int, n int, word string, i int) bool {
	// 如果当前位置不匹配，剪枝
	if board[m][n] != word[i] {
		return false
	}
	// 如果到达单词末尾, return true
	if i == len(word)-1 {
		return true
	}
	// 当前位置置为 "."
	board[m][n] = '.'
	// 继续往下走，判断
	for k := 0; k < 4; k++ {
		X := m + dirM[k]
		Y := n + dirN[k]
		if X >= 0 && X < len(board) && Y >= 0 && Y < len(board[0]) {
			if (dfs(board, X, Y, word, i+1)) {
				return true
			}
		}
	}
	// 重置当前位置
	board[m][n] = word[i]
	return false
}