"ABCESFCSADEE",3,4,"ABCCED"
true
"ABCESFCSADEE",3,4,"ABCB"
false
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param str string字符串 * @return bool布尔型 */ public boolean hasPath(String matrix, int rows, int cols, String str) { char[] MATRIX = matrix.toCharArray(); char[] STR = str.toCharArray(); //如果矩阵或者字符串无效则直接返回false if(MATRIX == null || rows < 1 || cols < 1 || STR == null) { return false; } //使用辅助矩阵标记,避免访问重复 boolean[] isVisited = new boolean[rows * cols]; int pathLength = 0; for(int row = 0; row < rows; row++) { for(int col =0; col <cols; col++) { //传入参数有原矩阵,原矩阵行数,原矩阵列数,矩阵当前元素的行下标,矩阵当前元素的列下标 //当前在矩阵中走过的路径长度,矩阵当前元素的访问状态 //该函数是递归调用,返回值是boolean类型,所以用另外函数来操作 if(hasPathCore(MATRIX, rows, cols, row, col, STR, pathLength, isVisited)) { return true; } } } //执行到这一步,说明矩阵中不存在路径匹配目标字符串,返回false即可 return false; } private boolean hasPathCore(char[] matrix,int rows,int cols, int row, int col, char[] str,int pathLength, boolean[] isVisited ) { //判断矩阵当前元素状态,如果不满足目标状态则返回false if(row < 0 || col < 0|| row >= rows || col >= cols || isVisited[row * cols + col] == true || str[pathLength] != matrix[row * cols + col]) { return false; } //当str[pathLength] = matrix[row * cols + col]时继续往下走 //只有一种情况return true if(pathLength == str.length - 1) { return true; } //默认无路径 boolean hasPath = false; //将当前元素访问状态置为true isVisited[row * cols + col] = true; hasPath = hasPathCore(matrix, rows, cols, row - 1, col, str, pathLength + 1, isVisited) || hasPathCore(matrix, rows, cols, row + 1, col, str, pathLength + 1, isVisited) || hasPathCore(matrix, rows, cols, row, col - 1, str, pathLength + 1, isVisited) || hasPathCore(matrix, rows, cols, row, col + 1, str, pathLength + 1, isVisited); /** * 回溯的过程 * 如果hasPath == false * 也就是当前路径字符中下标为pathLength的字符在矩阵中的定位不正确 * 我们需要回到前一个字符(pathLength - 1),然后重新定位 * 这时需要将矩阵中当前访问字符设置为未访问,isVisited[row * cols + col] = false * 因为已经没把它加入路径中,回溯上一个字符,在不同方向开始访问有可能再次访问到它 * 也就是复原 */ if(!hasPath) { isVisited[row * cols + col] = false; } return hasPath; } }
public boolean hasPath(String matrix, int rows, int cols, String str) { // write code here if (matrix == null || matrix.length() == 0) return false; if (str == null || str.length() == 0) return true; boolean[][] isUsed = new boolean[rows][cols];// 记录使用过的元素 for (int i = 0; i < rows; i++) {// 每个位置元素都开始一次 for (int j = 0; j < cols; j++) { if (helper(i, j, 0, matrix, str, isUsed)) return true; } } return false; } private boolean helper(int row, int col, int curIndex, String matrix, String str, boolean[][] isUsed) { // 检查范围、检查是否走过该点,检查是否已经str对应的字符串是否到头 if (row < 0 || row >= isUsed.length || col < 0 || col >= isUsed[0].length || isUsed[row][col] || curIndex >= str.length()) return false; if (str.charAt(curIndex) == matrix.charAt(row * isUsed[0].length + col)) { if (str.length() == curIndex + 1) return true; isUsed[row][col] = true; boolean result = helper(row - 1, col, curIndex + 1, matrix, str, isUsed);//上 if (result) return true;// 找到之后就不同向其他方向找,直接退出递归 result = helper(row + 1, col, curIndex + 1, matrix, str, isUsed);//下 if (result) return true; result = helper(row, col - 1, curIndex + 1, matrix, str, isUsed);//左 if (result) return true; result = helper(row, col + 1, curIndex + 1, matrix, str, isUsed);//右 if (result) return true; isUsed[row][col] = false;// 回溯 } return false; }
import java.util.*; public class Solution { //用于标记某个位置是否已经在当前路径中 static int[][] rec; static int rowN,colN; public boolean hasPath (String matrix, int rows, int cols, String str) { // write code here rowN = rows; colN = cols; rec = new int[rows][cols]; for(int r = 0; r < rows; r ++){ for(int c = 0; c < cols; c++){ //找到一个开始位置 //是否可以从任意一个位置开始遍历呢?即使当前位置的值不等于str.charAt(0),只要不把这个位置加入到路径中即可, //这种思路是错误的,会造成无法标记当前位置,从而导致死循环 if(matrix.charAt(r * colN + c) == str.charAt(0)){ boolean flag = helper(matrix,r,c,str); if(flag){ return true; } } } } return false; } public static boolean helper(String matrix,int r,int c, String restStr){ if(restStr.length() == 1){ return matrix.charAt(r * colN + c) == restStr.charAt(0); } if(matrix.charAt(r * colN + c) != restStr.charAt(0)){ return false; } //防止再次遍历到当前位置 rec[r][c] = 1; if(r - 1 >= 0 && rec[r - 1][c] == 0){ boolean up = helper(matrix,r - 1,c,restStr.substring(1)); if(up){ return true; } } if(r + 1 < rowN && rec[r + 1][c] == 0){ boolean down = helper(matrix,r + 1,c,restStr.substring(1)); if(down){ return true; } } if(c - 1 >= 0 && rec[r][c - 1] == 0){ boolean left = helper(matrix,r,c - 1,restStr.substring(1)); if(left){ return true; } } if(c + 1 < colN && rec[r][c + 1] == 0){ boolean right = helper(matrix,r,c + 1,restStr.substring(1)); if(right){ return true; } } //当一条路径遍历完成之后,可以再次访问当前位置 rec[r][c] = 0; return false; } }
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param matrix string字符串 # @param rows int整型 # @param cols int整型 # @param str string字符串 # @return bool布尔型 # class Solution: def hasPath(self, matrix, rows, cols, str): if len(str) > len(matrix): return False def judge(matrixs, strs, visited, rows, cols, i, j, k): visited_pos = i * cols + j if i < 0&nbs***bsp;i >= rows&nbs***bsp;j >= cols&nbs***bsp;visited[i][j] == True&nbs***bsp;matrixs[visited_pos] != strs[k]: return False if k == len(strs) - 1: return True visited[i][j] = True if judge(matrixs, strs, visited, rows, cols, i + 1, j, k + 1)&nbs***bsp;\ judge(matrixs, strs, visited, rows, cols, i - 1, j, k + 1)&nbs***bsp;\ judge(matrixs, strs, visited, rows, cols, i, j + 1, k + 1)&nbs***bsp;\ judge(matrixs, strs, visited, rows, cols, i, j - 1, k + 1): return True visited[i][j] = False return False visited = [[False] * cols for _ in range(rows)] for i in range(rows): for j in range(cols): if judge(matrix, str, visited, rows, cols, i, j, 0): return True return False # write code here
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param str string字符串 * @return bool布尔型 */ int getPosition(int i,int j,int rows,int cols){ return i*cols+j; } bool findPath(vector<vector<int> > label,string matrix,int i,int j,int rows,int cols,string& s,string str){ if(s==str) return true; if(s.size()>=str.size()) return false; if(i>0&&label[i-1][j]==0&&str[s.size()]==matrix[getPosition(i-1, j, rows, cols)]){ s.push_back(str[s.size()]); label[i-1][j]=1; if(findPath(label,matrix, i-1, j, rows, cols, s,str)) return true; label[i-1][j]=0; s.pop_back(); } if(i<rows-1&&label[i+1][j]==0&&str[s.size()]==matrix[getPosition(i+1, j, rows, cols)]){ s.push_back(str[s.size()]); label[i+1][j]=1; if(findPath(label,matrix, i+1, j, rows, cols, s,str)) return true; label[i+1][j]=0; s.pop_back(); } if(j>0&&label[i][j-1]==0&&str[s.size()]==matrix[getPosition(i, j-1, rows, cols)]){ s.push_back(str[s.size()]); label[i][j-1]=1; if(findPath(label,matrix, i, j-1, rows, cols, s,str)) return true; label[i][j-1]=0; s.pop_back(); } if(j<cols-1&&label[i][j+1]==0&&str[s.size()]==matrix[getPosition(i, j+1, rows, cols)]){ s.push_back(str[s.size()]); label[i][j+1]=1; if(findPath(label,matrix, i, j+1, rows, cols, s,str)) return true; label[i][j+1]=0; s.pop_back(); } return false; } bool hasPath(string matrix, int rows, int cols, string str) { // write code here bool ret=false; for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ vector<vector<int> > label(rows,vector<int>(cols,0)); label[i][j]=1; string s; s.push_back(matrix[getPosition(i, j, rows, cols)]); ret=findPath(label,matrix, i, j, rows, cols, s,str); if(ret) return true; } } return false; } };
效率算不上高,但是代码行数少
int row=0,col=0; public boolean hasPath (String matrix, int rows, int cols, String str) { // write code here char[] carr=matrix.toCharArray(),carrstr=str.toCharArray(); char[][] carr2=new char[rows][cols],carr3=new char[rows][cols]; row=rows;col=cols; int count=0; for(int i=0;i<rows;i++) for(int j=0;j<cols;j++) carr2[i][j]=carr[count++]; return findRoud(carr2,carr3,-1,-1,carrstr,0); } public boolean findRoud(char[][] carr2,char[][] carr3,int x,int y,char[] carrstr ,int k){ boolean flag=false; for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(carr2[i][j]==carrstr[k]&&carr3[i][j]!=1&&((Math.abs(x-i)==1&&y-j==0)||(Math.abs(y-j)==1&&x-i==0)||x==-1)){ char[][] tempArr=new char[row][col]; for(int m=0;m<row;m++)for(int n=0;n<col;n++)tempArr[m][n]=carr3[m][n]; tempArr[i][j]=1; if(k+1<carrstr.length)flag=findRoud(carr2,tempArr,i,j,carrstr,k+1); else flag= true; } if(flag==true)return true; } } return false; }
class Solution: # main def hasPath(self , matrix : str , rows : int , cols : int , string : str ): #1.special cases if len(string)>len(matrix): return False if len(matrix)!= rows*cols: return False if rows<0&nbs***bsp;cols<0: return False # 2.construct matrix by string matrixList = [] for i in range(rows): matrixList.append(list(matrix[i*cols:i*cols+cols])) #print(matrixList) #3.search the location of the String's first char,which is in the matrixlist firstCharAppearIndex = [] for row in range(rows): for col in range(cols): if matrixList[row][col]==string[0]: firstCharAppearIndex.append((row,col)) if len(firstCharAppearIndex)==0: return False #4.Traversal search the sequence,use recursion method for idxTuple in firstCharAppearIndex: if self.findResultPath(matrixList,idxTuple,string): return True # worst result,cannot find a path then return False return False def findResultPath(self, matrixList:list , idxTuple:tuple , string:str): # idxtuple(row,col) index location of the first character of string,that is string[0] # 1.special cases if (not 0<=idxTuple[0]<len(matrixList))&nbs***bsp;(not 0<=idxTuple[1]<len(matrixList[0]))&nbs***bsp;\ (matrixList[idxTuple[0]][idxTuple[1]]!=string[0]): return False if len(string)==1 and matrixList[idxTuple[0]][idxTuple[1]]==string[0]: return True # 2.search the surrounding element whether is equal to string[1] else: matrixList[idxTuple[0]][idxTuple[1]]="" res = self.findResultPath(matrixList=matrixList,idxTuple=(idxTuple[0],idxTuple[1]-1),string=string[1:]) \ &nbs***bsp;self.findResultPath(matrixList=matrixList,idxTuple=(idxTuple[0],idxTuple[1]+1),string=string[1:]) \ &nbs***bsp;self.findResultPath(matrixList=matrixList,idxTuple=(idxTuple[0]+1,idxTuple[1]),string=string[1:]) \ &nbs***bsp;self.findResultPath(matrixList=matrixList,idxTuple=(idxTuple[0]-1,idxTuple[1]),string=string[1:]) matrixList[idxTuple[0]][idxTuple[1]]=string[0] return res
private boolean[][] flags = null; public boolean hasPath (String matrix, int rows, int cols, String str) { // write code here if(matrix.length()<str.length()){return false;} char[][] store = new char[rows][cols]; //标记走过的位置 flags = new boolean[rows][cols]; //初始化 for(int i = 0;i<rows;i++){ for(int j = 0;j<cols;j++){ store[i][j] = matrix.charAt(i*cols+j); } } //遍历 for(int i = 0;i<store.length;i++){ for(int j = 0;j<store[i].length;j++){ if(dfs(store,i,j,str,0)){return true;} } } return false; } //回溯法深度搜索 public boolean dfs(char[][] store,int x,int y,String str,int curIndex){ //如果x或y超出边界,或者已走过,false if(x<0||x>=store.length||y<0||y>=store[x].length||flags[x][y]){return false;} //当前字符不相等,false if(store[x][y]!=str.charAt(curIndex)){return false;} //如果curIndex等于str长度,匹配完毕,true if(curIndex == str.length()-1){return true;} //设置标志 flags[x][y]= true; curIndex++; //分别对右下左上方向进行搜索 if(dfs(store,x,y+1,str,curIndex)||dfs(store,x+1,y,str,curIndex)|| dfs(store,x-1,y,str,curIndex)|| dfs(store,x,y-1,str,curIndex)){ return true; } //退栈,设置为false flags[x][y]=false; return false; }
class Solution: def hasPath(self , matrix , rows , cols , str ): # write code here if str == '': return True if not matrix: return False dp = [[0]*cols for i in range(rows)] for i in range(len(matrix)): row = i // cols col = i % cols dp[row][col] = matrix[i] matrix = dp def dfs(i, j, k): if not 0 <= i < len(matrix)&nbs***bsp;\ not 0 <= j < len(matrix[0])&nbs***bsp; matrix[i][j] != str[k]: # 系好安全带 return False if k == len(str) - 1: return True matrix[i][j] = '' res = dfs(i + 1, j, k + 1)&nbs***bsp;\ dfs(i - 1, j, k + 1)&nbs***bsp;\ dfs(i, j + 1, k + 1)&nbs***bsp;\ dfs(i, j - 1, k + 1) matrix[i][j] = str[k] return res # 遍历board,当有一条满足路径的路线时,就可以返回算是成功 for i in range(rows): for j in range(cols): if dfs(i, j, 0): return True return False
import java.util.*; public class Solution { boolean[][] isVisited; public boolean hasPath (String matrix, int rows, int cols, String str) { if(matrix==null || matrix.length()==0 || rows<1 || cols<1 || cols*rows!=matrix.length() || str.length()>matrix.length()){ return false; } isVisited=new boolean[rows][cols]; char[][] mx=new char[rows][cols]; char[] cs=str.toCharArray(); int k=0; for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ mx[i][j]=matrix.charAt(k++); } } for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(dfs(mx,cs,0,i,j)){ return true; } } } return false; } private boolean dfs(char[][] matrix,char[] cs,int index,int row,int col){ if(index==cs.length){ return true; } if(row<0 || row>=matrix.length || col<0 || col>=matrix[0].length){ return false; } if(isVisited[row][col]){ return false; } if(matrix[row][col]!=cs[index]){ return false; } isVisited[row][col]=true; boolean temp=dfs(matrix,cs,index+1,row+1,col) || dfs(matrix,cs,index+1,row-1,col) || dfs(matrix,cs,index+1,row,col+1) || dfs(matrix,cs,index+1,row,col-1); isVisited[row][col]=false; return temp; } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param str string字符串 * @return bool布尔型 */ int rows; int cols; bool hasPath(string matrix, int row, int col, string str) { // write code here if (str.empty()&&matrix.empty()) return true; if (str.empty()) return false; rows=row; cols=col; vector<vector<char>> c; for(int i=0;i<rows;i++){ vector<char> b; for(int j=0;j<cols;j++){ b.push_back(0); } c.push_back(b); } vector<vector<char>> a; int n=0; for(int i=0;i<rows;i++){ vector<char> b; for(int j=0;j<cols;j++){ b.push_back(matrix[n++]); } a.push_back(b); } for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(find(c,a,i,j,str,0)) return true; } } return false; } bool find(vector<vector<char>> c,vector<vector<char>> a,int r,int d,string str,int num){ if(r<0||d<0||r>=rows||d>=cols||num>=str.size()||c[r][d]!=0) return false; if(a[r][d]==str[num]&&num==str.size()-1) return true; if (a[r][d]==str[num]){ c[r][d]++; return find(c,a,r-1,d,str,num+1)||find(c,a,r,d-1,str,num+1) ||find(c,a,r+1,d,str,num+1)||find(c,a,r,d+1,str,num+1); } else return false; } };
public class Solution { //定义了一个函数用来把题目中传入的Sring矩阵转换成二维数组,这样便于理解 private char[][] changeStrToArray(String matrix, int rows, int cols) { char[][] Matrix = new char[rows][cols]; int count = 0; for(int i=0;i<rows; i++) for(int j=0;j<cols;j++) Matrix[i][j] = matrix.charAt(count++); return Matrix; } //判断该点是不是正确路径的首个点 private boolean hasPathCore(char[][] Matrix, int rows, int cols, int row, int col, int length, String str, boolean[][] visited) { if(length == str.length()) //当创建的路径长度等于目标str的长度后,说明匹配完成,返回true; return true; boolean hasPath = false; //首先创建一个boolean变量初始化为false if(row >= 0 && row <rows && col >= 0 && col <cols && str.charAt(length) == Matrix[row][col] && visited[row][col] == false ){ //当此时row和col都在范围内且字符等于str上下一个正确字符且该字符还未被加入到路径中时 length++; //首先将完成好的路径加1 visited[row][col]=true;//然后将该点置为已读 hasPath = hasPathCore(Matrix, rows, cols, row + 1, col, length, str, visited) || hasPathCore(Matrix, rows, cols, row - 1, col, length, str, visited) || hasPathCore(Matrix, rows, cols, row, col + 1, length, str, visited) || hasPathCore(Matrix, rows, cols, row, col - 1, length, str, visited); //将四个可能路径用或逻辑符并起来 if(!hasPath){ //回溯法的精髓,当目前的点接下来的四个可能路径(上下左右)都无法匹配下一个字符时,说明这个目前的点虽然满足条件,但是接下来不满足条件,所以要回溯这个点(把length减一,并把它的已读状态改回未读,回到上一个点的判断函数里) length--; visited[row][col] = false; } } return hasPath; } public boolean hasPath (String matrix, int rows, int cols, String str) { // 特殊情况 if(matrix == null || rows < 1 || cols < 1 || str == null) return false; //状态数组,记录每个点是否已经被加入到路径中,初始未加入为false,已加入为true。 boolean[][] visited = new boolean[rows][cols]; char[][] Matrix = changeStrToArray(matrix, rows, cols); //循环数组里的每个点,用hasPathCore判断是否能组成正确路径 for(int row=0;row<rows;row++) for(int col=0;col<cols;col++) if(hasPathCore(Matrix, rows, cols, row, col, 0, str, visited)) return true; return false; } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param str string字符串 * @return bool布尔型 */ bool res=0; int y=0; bool hasPath(string matrix, int rows, int cols, string str) { // write code here if(str.size()==0)return true; y=cols;vector<bool> vis(matrix.size()); for(int i=0;i<matrix.size();i++) { string temp; if(matrix[i]==str[0]) { temp+=matrix[i];vis[i]=true; dfs(matrix,temp,str,i,vis); vis[i]=false; } } return res; } void dfs(string &s,string &temp,string &str,int pos,vector<bool>&vis ) { if(temp==str){res=true;return;} int dx[]={-y,y,-1,1}; for(int i=0;i<4;i++) { int npos=pos+dx[i]; if(npos<0||npos>=s.size()||vis[npos])continue; if(temp.size()<str.size()&&s[npos]==str[temp.size()]) { temp+=s[npos]; vis[npos]=true; if(temp==str) { res=true;return; } dfs(s,temp,str,npos,vis); vis[npos]=false; temp=temp.substr(0,temp.size()-1); } } return ; } };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param str string字符串 * @return bool布尔型 */ bool find_str(int c_rows, int c_cols, int str_index, string str, vector<vector<char>>& matrix_str, vector<vector<bool>>& table) { int rows = table.size(); int cols = table[0].size(); bool result = false; char word = matrix_str[c_rows][c_cols]; char word_str = str[str_index]; if (str_index == str.length() - 1 && str[str_index] == matrix_str[c_rows][c_cols]) { result = true; return result; } if(str[str_index] == matrix_str[c_rows][c_cols]) { if (c_rows - 1 >= 0 && !table[c_rows - 1][c_cols]) { table[c_rows - 1][c_cols] = true; str_index++; result = find_str(c_rows - 1, c_cols, str_index, str, matrix_str, table); if(result) { return result; } table[c_rows - 1][c_cols] = false; str_index--; } if (c_rows + 1 < rows && !table[c_rows + 1][c_cols]) { table[c_rows + 1][c_cols] = true; str_index++; result = find_str(c_rows + 1, c_cols, str_index, str, matrix_str, table); if(result) { return result; } table[c_rows + 1][c_cols] = false; str_index--; } if (c_cols - 1 >= 0 && !table[c_rows][c_cols - 1]) { table[c_rows][c_cols - 1] = true; str_index++; result = find_str(c_rows, c_cols - 1, str_index, str, matrix_str, table); if(result) { return result; } table[c_rows][c_cols - 1] = false; str_index--; } if (c_cols + 1 < cols && !table[c_rows][c_cols + 1]) { table[c_rows][c_cols + 1] = true; str_index++; result = find_str(c_rows, c_cols + 1, str_index, str, matrix_str, table); if(result) { return result; } table[c_rows][c_cols + 1] = false; str_index--; } } return result; } bool hasPath(string matrix, int rows, int cols, string str) { // write code here vector<vector<char>> matrix_str(rows, vector<char>(cols)); int matrix_index = 0; for(int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { matrix_str[i][j] = matrix[matrix_index]; matrix_index++; } cout << endl; } bool result = false; for(int i = 0; i < rows; i++) { for(int j = 0; j < cols; j++) { vector<vector<bool>> table(rows, vector<bool>(cols, false)); table[i][j] = true; result = find_str(i, j, 0, str, matrix_str, table); if(result) { return result; } } } return result; } };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param str string字符串 * @return bool布尔型 */ int m,n,visit[1000][1000],ll; char mmap[1000][1000]; string tempstr; string sstr; int flag = 0; void dfs(int x,int y,int l){ if(x<0||x>=m||y<0||y>=n||l>=ll){ return; } if(!visit[x][y]){ visit[x][y] = 1; tempstr += mmap[x][y]; if(tempstr[l] == sstr[l]){//依次比较每一位,不同就停止 if(tempstr == sstr){ flag = 1; return ; } l++; dfs(x,y+1,l); dfs(x+1,y,l); dfs(x,y-1,l); dfs(x-1,y,l); } tempstr.pop_back();; visit[x][y] = 0; } return ; } bool hasPath(string matrix, int rows, int cols, string str) { // write code here int k = 0; ll = str.length(); int len = matrix.length(); for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ mmap[i][j] = matrix[k++];//把字符地图做好 } } memset(visit,0,sizeof(visit)); m = rows; n = cols; tempstr = ""; sstr = str; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ dfs(i,j,0);//地图上的每个点作为起点,去找路径。 if(flag==1) return true; tempstr = ""; memset(visit,0,sizeof(visit)); } } return false; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param matrix string字符串 * @param rows int整型 * @param cols int整型 * @param str string字符串 * @return bool布尔型 */ public boolean hasPath (String matrix, int rows, int cols, String str) { // write code here char[][] board=new char[rows][cols]; int k=0; for(int i=0; i<rows; i++){ for(int j=0; j<cols; j++){ board[i][j]=matrix.charAt(k++); } } boolean[][] visited=new boolean[rows][cols]; for(int i=0; i<rows; i++){ for(int j=0; j<cols; j++){ if(dfs(board,i,j,visited,str,0)) return true; } } return false; } private boolean dfs(char[][] board,int i,int j,boolean[][] visited,String str,int k){ if(i<0 || i>=board.length || j<0 || j>=board[0].length || visited[i][j]) return false; if(board[i][j]!=str.charAt(k)) return false; if(k==str.length()-1) return true; visited[i][j]=true; boolean res=dfs(board,i+1,j,visited,str,k+1) || dfs(board,i-1,j,visited,str,k+1) || dfs(board,i,j+1,visited,str,k+1) || dfs(board,i,j-1,visited,str,k+1); visited[i][j]=false; return res; } }