这道题写得是真滴难受啊,为啥一维数组和二维数组要混着用呢。。。没太搞懂。
这道题可以使用递归+回溯的方法进行求解
· 递归终止条件为:如果匹配成功则返回true;如果下标越界或者已经访问过或者字符不匹配,则返回false
然后便可以递归地向上下左右寻找是否有匹配的字符,若找到了路径则返回ture,否则返回false;
boolean dfs(int row, int col, int pnt) { if(pnt == str.length) return true; if (row > rows - 1 || col > cols - 1 || row < 0 || col < 0) return false; if (vis[row][col] == 1) return false; if (this.matrix[row * cols + col] != str[pnt]) return false; vis[row][col] = 1; boolean f1, f2, f3, f4; f1 = dfs(row + 1, col, pnt + 1); // 向下 f2 = dfs(row - 1, col, pnt + 1); // 向上 f3 = dfs(row, col + 1, pnt + 1); // 向右 f4 = dfs(row, col - 1, pnt + 1); // 向左 vis[row][col] = 0; // 以便下一条路径可以访问 return f1 || f2 || f3 || f4; }