AlgoPressAppearance
12-矩阵中的路径
题目描述
https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/
给定一个 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 仅由大小写英文字母组成
注意：本题与主站 79 题相同：https://leetcode.cn/problems/word-search/
思路分析
回溯法
第1步，首先 for循环整个数组，任意一个字符都可能是开始。
第2步，传入当前坐标和 word 的 index，如果当前的值和 word index的字符是相等的，则继续下一步
第3步，判断当前坐标的相邻的4个单元格，有任何一个是和word index是相等的，则继续下一步递归判断
因为不能重复放置，所以需要另外一个数组记录了放置的值
第4步，如果执行到 word index的结束，则返回true，如果相邻的单元格已经被放置，或者和下一个word index的值都不相等，则return false
实现代码
csharp
public class Solution {
// 基本思路：开辟一个一样的数组用来存储是否被访问过
// 从第一个单元格循环
// 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 即可。
private bool IsExist(char[][] board, int[][] visited, string word, int boardRow, int boardCol, int wordIndex){
//如果全访问完了，说明存在
if(wordIndex >= word.Length){
return true;
}
if(boardRow < 0 || boardRow >= board.Length || boardCol < 0 || boardCol >= board[0].Length || board[boardRow][boardCol] != word[wordIndex] || visited[boardRow][boardCol] == 1 ){
//如果越界直接返回 false
return false;
}
visited[boardRow][boardCol] = 1 ;
//探测四个方向
bool result = IsExist(board,visited,word,boardRow+1,boardCol,wordIndex+1)
|| IsExist(board,visited,word,boardRow-1,boardCol,wordIndex+1)
|| IsExist(board,visited,word,boardRow,boardCol+1,wordIndex+1)
|| IsExist(board,visited,word,boardRow,boardCol-1,wordIndex+1);
//取回该棋子
visited[boardRow][boardCol] = 0;
return result;
}
public bool Exist(char[][] board, string word) {
if(board.Length == 0 || board == null || word == ""){
return false;
}
//初始化记录数组
int[][] visited = new int[board.Length][];
for(int i=0; i<board.Length; i++){
visited[i] = new int[board[0].Length];
}
bool result = false;
for(int i = 0; i < board.Length; i++){
for(int j = 0; j < board[0].Length; j++){
result = IsExist(board, visited, word,i, j, 0);
if(result == true){
return result;
}
}
}
return result;
}
}
实现代码（第二遍）
csharp
public class Solution {
private bool[,] visited;
private bool Exist(char[][] board, string word, int i, int j, int index){
if(index == word.Length){ //已经匹配完所有数字，返回 true
return true;
}
//越界或者不匹配，或者已经放置
if(i<0 || j<0 || i>=board.Length || j>=board[0].Length || board[i][j] != word[index] || visited[i,j] == true){
return false;
}
//说明可以继续
//放置
visited[i,j] = true;
//判断是否可以继续，只能朝4个方向走
bool result = Exist(board,word,i,j+1,index+1)
|| Exist(board,word,i,j-1,index+1)
|| Exist(board,word,i+1,j,index+1)
|| Exist(board,word,i-1,j,index+1);
//取回
visited[i,j] = false;
return result;
}
public bool Exist(char[][] board, string word) {
bool result = false;
visited = new bool[board.Length, board[0].Length];
for(int i=0; i<board.Length; i++){
for(int j=0; j<board[0].Length; j++){
result = result || Exist(board,word,i,j,0);
if(result){
return true;
}
}
}
return result;
}
}
实现代码：复习20220503
csharp
public class Solution {
bool[,] visited;
public bool Exist(char[][] board, string word) {
int m = board.Length;
int n = board[0].Length;
visited = new bool[m,n];
//回溯法试探
//选择任意一个点作为起始
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(IsExist(board,word,i,j,0)){
return true;
}
}
}
return false;
}
private bool IsExist(char[][] board, string word, int i, int j, int wordIndex){
//放置完
if(wordIndex == word.Length){
return true;
}
//检查越界 或者占用
if(i<0 || j<0 || i==board.Length || j==board[0].Length || visited[i,j] || board[i][j] != word[wordIndex]){
return false;
}
//放置
visited[i,j] = true;
//放置其他四个地方
bool result = IsExist(board,word,i-1,j,wordIndex+1)
||IsExist(board,word,i+1,j,wordIndex+1)
||IsExist(board,word,i,j-1,wordIndex+1)
||IsExist(board,word,i,j+1,wordIndex+1) ;
//取回
visited[i,j] = false;
return result;
}
}