【剑指offor】面试题12：矩阵中的路径

题目描述

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

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

例如&＃xff0c;在下面的 3×4 的矩阵中包含单词 “ABCCED”&＃xff08;单词中的字母已标出&＃xff09;。

代码

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定&＃xff0c;请勿修改&＃xff0c;直接返回方法规定的值即可** * &＃64;param matrix char字符型vector> * &＃64;param word string字符串 * &＃64;return bool布尔型*/bool hasPath(vector<vector<char> >& board, string word) {// write code herefor(int i &＃61; 0; i < board.size(); i&＃43;&＃43;)//实现矩阵每个点都可以是起点for(int j &＃61; 0; j < board[i].size(); j&＃43;&＃43;)if(dfs(board,word,0,i,j)) return true;return false; }int dx[4] &＃61; {-1,0,1,0}, dy[4] &＃61; {0,1,0,-1}; //方向数组bool dfs(vector<vector<char>>& board, string& word,int u,int x,int y){if(board[x][y] !&＃61; word[u]) return false;//这里就是比较字符的地方&＃xff0c;不等能过去&＃xff0c;可不就是等了呗。if(u &＃61;&＃61; word.size() - 1) return true;char t &＃61; board[x][y];board[x][y] &＃61; &＃39;.&＃39;;//来区别这个点是否被访问过for(int i &＃61; 0; i < 4; i&＃43;&＃43;){int a &＃61; x &＃43; dx[i], b &＃61; y &＃43; dy[i];//出界或者走到已经搜索过的位置if(a < 0 || a >&＃61; board.size() || b < 0 || b >&＃61; board[0].size() || board[a][b] &＃61;&＃61; &＃39;.&＃39;) continue;if(dfs(board,word,u&＃43;1,a,b)) return true;//只有上面的u&＃61;size-1返回true&＃xff0c;你这里才会返回true}board[x][y] &＃61; t;//访问错误&＃xff0c;将原来的字符还原return false;//说明当前点的上下左右都走不通&＃xff0c;你要返回到上一层&＃xff0c;当然最终也可能返回到重新选一个起点的情况。}
};