[编程题]矩阵中的路径
- 热度指数：436970 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
示例1
输入
"ABCESFCSADEE",3,4,"ABCCED"
输出
true
示例2
输入
"ABCESFCSADEE",3,4,"ABCB"
输出
false
回溯
基本思想：
0.根据给定数组，初始化一个标志位数组，初始化为false，表示未走过，true表示已经走过，不能走第二次
1.根据行数和列数，遍历数组，先找到一个与str字符串的第一个元素相匹配的矩阵元素，进入judge
2.根据i和j先确定一维数组的位置，因为给定的matrix是一个一维数组
3.确定递归终止条件：越界，当前找到的矩阵值不等于数组对应位置的值，已经走过的，这三类情况，都直接false，说明这条路不通
4.若k，就是待判定的字符串str的索引已经判断到了最后一位，此时说明是匹配成功的
5.下面就是本题的精髓，递归不断地寻找周围四个格子是否符合条件，只要有一个格子符合条件，就继续再找这个符合条件的格子的四周是否存在符合条件的格子，直到k到达末尾或者不满足递归条件就停止。
6.走到这一步，说明本次是不成功的，我们要还原一下标志位数组index处的标志位，进入下一轮的判断。
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
//标志位，初始化为false
boolean[] flag = new boolean[matrix.length];
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
//循环遍历二维数组，找到起点等于str第一个元素的值，再递归判断四周是否有符合条件的----回溯法
if(judge(matrix,i,j,rows,cols,flag,str,0)){
return true;
}
}
}
return false;
}
//judge(初始矩阵，索引行坐标i，索引纵坐标j，矩阵行数，矩阵列数，待判断的字符串，字符串索引初始为0即先判断字符串的第一位)
private boolean judge(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,char[] str,int k){
//先根据i和j计算匹配的第一个元素转为一维数组的位置
int index = i*cols+j;
//递归终止条件
if(i<0 || j<0 || i>=rows || j>=cols || matrix[index] != str[k] || flag[index] == true)
return false;
//若k已经到达str末尾了，说明之前的都已经匹配成功了，直接返回true即可
if(k == str.length-1)
return true;
//要走的第一个位置置为true，表示已经走过了
flag[index] = true;
//回溯，递归寻找，每次找到了就给k加一，找不到，还原
if(judge(matrix,i-1,j,rows,cols,flag,str,k+1) ||
judge(matrix,i+1,j,rows,cols,flag,str,k+1) ||
judge(matrix,i,j-1,rows,cols,flag,str,k+1) ||
judge(matrix,i,j+1,rows,cols,flag,str,k+1) )
{
return true;
}
//走到这，说明这一条路不通，还原，再试其他的路径
flag[index] = false;
return false;
}
}
发表于 2018-04-29 10:54:12
回复(61)
/**
用一个状态数组保存之前访问过的字符，然后再分别按上，下，左，右递归
*/
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
int flag[] = new int[matrix.length];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (helper(matrix, rows, cols, i, j, str, 0, flag))
return true;
}
}
return false;
}
private boolean helper(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, int[] flag) {
int index = i * cols + j;
if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == 1)
return false;
if(k == str.length - 1) return true;
flag[index] = 1;
if (helper(matrix, rows, cols, i - 1, j, str, k + 1, flag)
|| helper(matrix, rows, cols, i + 1, j, str, k + 1, flag)
|| helper(matrix, rows, cols, i, j - 1, str, k + 1, flag)
|| helper(matrix, rows, cols, i, j + 1, str, k + 1, flag)) {
return true;
}
flag[index] = 0;
return false;
}
}
发表于 2015-08-20 15:37:31
回复(66)
class Solution {
public:
/*
大家好，我是yishuihan，这个题目是回溯法的典型题目；
还有八皇后问题也是经典的回溯法例题，大家可以参考;在《剑指offer》书中也给出了八皇后问题的思路；
不过，那个是在全排列问题中引出来的。其实回溯法也是全排列的一种方案，在本题中，也就是尝试了
matrix矩阵中所有点作为起点的方法，然后依据这个点进行向四个方向的递归；
在递归中，不满足题目的会自动出栈回到上一个状态；
*/
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if(matrix==NULL||rows<1||cols<1||str==NULL) return false;
bool *flag=new bool[rows*cols];
memset(flag,false,rows*cols);
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(haha(matrix,rows,cols,i, j,str,0,flag))
{
return true;
}
}
}
delete[] flag;
return false;
}
/*参数说明*/
bool haha(char* matrix,int rows,int cols,int i,int j,char* str,int k,bool* flag)
{
//因为是一维数组存放二维的值，index值就是相当于二维数组的（i，j）在一维数组的下标
int index = i * cols + j;
//flag[index]==true,说明被访问过了，那么也返回true;
if(i<0 || i>=rows || j<0 || j>=cols || matrix[index]!=str[k] || flag[index]==true)
return false;
//字符串已经查找结束，说明找到该路径了
if(str[k+1]=='\0') return true;
//向四个方向进行递归查找,向左，向右，向上，向下查找
flag[index] = true;//标记访问过
if( haha(matrix, rows, cols, i - 1, j, str, k + 1, flag)
||haha(matrix, rows, cols, i + 1, j, str, k + 1, flag)
||haha(matrix, rows, cols, i, j - 1, str, k + 1, flag)
||haha(matrix, rows, cols, i, j + 1, str, k + 1, flag))
{
return true;
}
flag[index] = false;
return false;
}
};
编辑于 2016-08-07 22:26:25
回复(15)
PYTHON 回溯法
# -*- coding:utf-8 -*-
#回溯法
#遍历矩阵中的每一个位置
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
if not matrix:
return False
if not path:
return True
x = [list(matrix[cols*i:cols*i+cols]) for i in range(rows)]
for i in range(rows):
for j in range(cols):
if self.exist_helper(x, i, j, path):
return True
return False
def exist_helper(self, matrix, i, j, p):
if matrix[i][j] == p[0]:
if not p[1:]:
return True
matrix[i][j] = ''
if i > 0 and self.exist_helper(matrix, i-1, j, p[1:]):
return True
if i < len(matrix)-1 and self.exist_helper(matrix, i+1, j ,p[1:]):
return True
if j > 0 and self.exist_helper(matrix, i, j-1, p[1:]):
return True
if j < len(matrix[0])-1 and self.exist_helper(matrix, i, j+1, p[1:]):
return True
matrix[i][j] = p[0]
return False
else:
return False
发表于 2018-08-19 17:00:46
回复(19)
python solution:
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, board, row, col, word):
self.col, self.row = col, row
board = [list(board[col * i:col * i + col]) for i in range(row)]
for i in range(row):
for j in range(col):
if board[i][j] == word[0]:
self.b = False
self.search(board, word[1:], [(i, j)], i, j)
if self.b:
return True
return False
def search(self, board, word, dict, i, j):
if word == "":
self.b = True
return
if j != 0 and (i, j - 1) not in dict and board[i][j - 1] == word[0]:
self.search(board, word[1:], dict + [(i, j - 1)], i, j - 1)
if i != 0 and (i - 1, j) not in dict and board[i - 1][j] == word[0]:
self.search(board, word[1:], dict + [(i - 1, j)], i - 1, j)
if j != self.col - 1 and (i, j + 1) not in dict and board[i][j + 1] == word[0]:
self.search(board, word[1:], dict + [(i, j + 1)], i, j + 1)
if i != self.row - 1 and (i + 1, j) not in dict and board[i + 1][j] == word[0]:
self.search(board, word[1:], dict + [(i + 1, j)], i + 1, j)
发表于 2017-10-31 22:58:59
回复(20)
【java】标准的带记忆DFS搜索，提供递归和非递归 两种 方法，了解一下。
一，标准的DFS，非递归，了解一下
思路：带记忆的BFS或者DFS，
需要辅助容器帮助记录路径，选用栈stack，还需要标记是否遍历过，用boolean[] visited
1.DFS深度优先，
进：peek一次，str的位子index++，对应位子visited[i+j*rows]=true，
进：peek一次，str的位子index++，对应位子visited[i+j*rows]=true，
并且把周围合适的点（上下左右&&字符匹配&&未遍历）加入到stack中
退:当前遍历过，复位：visited设为false，并且s.pop移除当前元素，str的位置减一
2.如果str匹配成功就返回true
是不是看起来很简单，接下来看实现
退:当前遍历过，复位：visited设为false，并且s.pop移除当前元素，str的位置减一
2.如果str匹配成功就返回true
是不是看起来很简单，接下来看实现
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
if(matrix == null || matrix.length != rows * cols
|| str == null || str.length == 0
|| str.length > matrix.length) return false;
boolean[] visited = new boolean[matrix.length];
for (int j = 0; j < rows; j++) {
for (int i = 0; i < cols; i++) {//每个节点都有可能是起点
if(dfs(matrix,rows,cols,str,i,j,visited)) return true;
}
}
return false;
}
//这里方便遍历上下左右
private static int[] x = {0,1,0,-1};//顺时针
private static int[] y = {1,0,-1,0};//顺时针
//这里复用了boolean[] visited 减少内存开销
private boolean dfs(char[] matrix, int rows, int cols, char[] str, int i, int j, boolean[] visited) {
if(matrix[i + j * cols] != str[0]) return false;//第一个字符必须相等
Stack<Integer> s = new Stack<>();//存的是坐标
int index = 0;//当前str的索引
s.push(i + j * cols);
while(!s.empty()) {
int location = s.peek();
if(visited[location] == true){//访问过,全部复位
visited[location] = false;//取消访问记录
s.pop();//退出该节点
if(--index < 0) return false;
continue;//防止该路径再次遍历
}
visited[location] = true;//标记已访问
if(++index == str.length) return true;//如果这个字符恰好是最后一个字符，直接返回true
/*
* 将当前节点周围(上下左右)符合标准的点加入到s中,
* 1.边界条件：i = location % cols j = location / cols i和j判断边界
* 2.必须未遍历过visited[cur] == false
* 3.当前字符匹配matrix[cur] == str[index]
*/
for (int k = 0; k < 4; k++) {
int xn = location % cols + x[k];
int yn = location / cols + y[k];
int cur = xn + yn * cols;
if(xn >= 0 && xn < cols && yn >= 0
&& yn < rows && visited[cur] == false
&& matrix[cur] == str[index]) {
s.push(cur);
}
}
}
return false;
} 二,前面大佬都是递归，没有新意，为了保证完整性，还是加上，递归也确实容易理解，代码简单
用递归来实现DFS
1.确定出口：
false:1.边界条件不满足，2.当前字符不匹配，3.已经遍历过
true：字符串str已经遍历结束
2.递：设置访问过
递归方式，按照上下左右递归
3.归：复位，未访问
1.确定出口：
false:1.边界条件不满足，2.当前字符不匹配，3.已经遍历过
true：字符串str已经遍历结束
2.递：设置访问过
递归方式，按照上下左右递归
3.归：复位，未访问
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
if(matrix == null || matrix.length != rows * cols
|| str == null || str.length == 0
|| str.length > matrix.length) return false;
boolean[] visited = new boolean[matrix.length];
for (int j = 0; j < rows; j++) {
for (int i = 0; i < cols; i++) {//每个节点都有可能是起点
if(dfs(matrix,rows,cols,str,i,j,0,visited)) return true;
}//这里多了个k=0来充当str的索引
}
return false;
}
//递归开始，真是短啊
private boolean dfs(char[] matrix, int rows, int cols, char[] str, int i, int j, int k,
boolean[] visited) {
if(i < 0 || i >= cols || j < 0 || j >= rows
|| visited[i + j * cols] || matrix[i + j * cols] != str[k])
return false;
if(k == str.length - 1) return true;//出口
visited[i + j * cols] = true;//递
if(dfs(matrix, rows, cols, str, i, j - 1, k + 1, visited)
|| dfs(matrix, rows, cols, str, i + 1, j, k + 1, visited)
|| dfs(matrix, rows, cols, str, i, j + 1, k + 1, visited)
|| dfs(matrix, rows, cols, str, i - 1, j, k + 1, visited))
return true;
visited[i + j * cols] = false;//归
return false;
}
编辑于 2018-06-15 17:46:39
回复(5)
//所谓的回溯无非就是对使用过的字符进行标记后和处理后的去标记
class Solution {
bool hasPathRecu(char* matrix, int rows, int cols, int row, int col, char *str, int length, vector<bool> used)
{
if(length==strlen(str))
return true;
if(row<0||row>=rows||col<0||col>=cols)
return false;
int index = col + row*cols;
bool result = false;
if( !used[index] && matrix[index]==str[length]){
used[index] = true;
result = hasPathRecu(matrix, rows, cols, row-1, col, str, length+1, used)|| hasPathRecu(matrix, rows, cols, row+1, col, str, length+1, used)
||hasPathRecu(matrix, rows, cols, row, col+1, str, length+1, used)||hasPathRecu(matrix, rows, cols, row, col-1, str, length+1, used);
used[index] = false;
}
if(result)
return true;
return false;
}
public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
vector<bool> used(strlen(matrix),false);
if(str==NULL) return true;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(hasPathRecu(matrix, rows, cols, i, j, str, 0, used))
return true;
}
}
return false;
}
};
发表于 2016-05-03 10:59:38
回复(11)
/**
@author zhengyanan
@date 2017/3/14 @time 10:07
version_2:
核心思路：优化版回溯法，参考《剑指offer》
1.将matrix字符串模拟映射为一个字符矩阵(但并不实际创建一个矩阵)
2.取一个boolean[matrix.length]标记某个字符是否已经被访问过。
3.如果没找到结果，需要将对应的boolean标记值置回false,返回上一层进行其他分路的查找。
运行时间：37ms
占用内存：528k
*/
public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
boolean[] visited = new boolean[matrix.length];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (searchFromHere(matrix,rows,cols,i,j,0,str,visited))
return true;
}
}
// System.out.println(Arrays.toString(visited));
return false;
}
public boolean searchFromHere(char[] matrix,int rows,int cols,int r,int c,int index,char[] str,boolean[] visited){
if (r < 0 || r >= rows || c < 0 || c >= cols || matrix[r * cols + c] != str[index] || visited[r * cols + c])
return false;
if (index == str.length - 1) return true;
visited[r * cols + c] = true;
if (searchFromHere(matrix,rows,cols,r - 1,c,index + 1,str,visited) ||
searchFromHere(matrix,rows,cols,r,c -1,index + 1,str,visited) ||
searchFromHere(matrix,rows,cols,r + 1,c,index + 1,str,visited) ||
searchFromHere(matrix,rows,cols,r,c + 1,index + 1,str,visited))
return true;
visited[r * cols + c] = false;
return false;
}
/**
@author zhengyanan
@time 22:10
@description
version_1:
核心思路：回溯法
1.先将matrix字符串映射为字符矩阵；
2.从原字符串中找到第一个跟str[0]相等的字符，得到其对应的在矩阵中的位置[r,c]
1）从[r,c]开始按 上、左、右、下的顺序搜索；
2）每当搜索到一个节点，先判断path是否包括它，包括就说明已经经过此节点，不能
再经过了；如果不包括，就将其加入path容器
3）直到搜索到str[length - 1]节点，说明成功找到，标记result为true，标记
isFinished为true,尽快结束所有的递归操作
4）如果某节点起的 上、左、右、下 都搜索过但还没找到结果，说明经过此节点的路
径都不满足题意，将其从path中删除，回溯到上一层继续找。
（PS:确实是回溯法，不过代码有点长，实现的有点繁杂）
运行时间：51ms
占用内存：625k
*/
// private char[][] data;
// private int rows;
// private int cols;
// private LinkedList<Integer> path = new LinkedList<Integer>();
// private boolean result = false;
// private boolean isFinished = false;
//
// public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
// this.rows = rows;
// this.cols = cols;
// data = new char[rows][cols];
// for (int i = 0,k = 0; i < rows; i ++) {
// for (int j = 0; j < cols; j ++) {
// data[i][j] = matrix[k ++];
// }
// }
//
// int r,c;
// for (int i = 0; i < matrix.length; i++) {
// if (matrix[i] == str[0] && !isFinished){
// r = i / cols;
// c = i % cols;
// tryPath(r,c,str,0);
// }
// }
//
// return result;
// }
//
// public void tryPath(int r,int c,char[] str,int index){
// if (isFinished) return;
// if (path.contains(r * cols + c)) return;
//
// path.addLast(r * cols + c);
//
// if (index == str.length - 1) {
// isFinished = true;
// result = true;
// }
// else {
// for (int i = 0; i < 4; i++) {
// switch (i) {
// case 0:
// if (r - 1 >= 0 && data[r - 1][c] == str[index + 1]) {
// tryPath(r - 1, c, str, index + 1);
// }
// break;
// case 1:
// if (c - 1 >= 0 && data[r][c - 1] == str[index + 1]) {
// tryPath(r, c - 1, str, index + 1);
// }
// break;
// case 2:
// if (r + 1 < rows && data[r + 1][c] == str[index + 1]) {
// tryPath(r + 1, c, str, index + 1);
// }
// break;
// case 3:
// if (c + 1 < cols && data[r][c + 1] == str[index + 1]) {
// tryPath(r, c + 1, str, index + 1);
// }
// break;
// }
// }
// }
// path.removeLast();
// }
编辑于 2017-03-14 10:50:27
回复(3)
无需额外的空间
class Solution {
public:
bool dfs(char* matrix, int rows, int cols, char* str, int i,
int j){
if(!str || !(*str)) return true;
bool ans = false;
if((i>=0) && (i<rows) && (j>=0)
&& (j<cols) && (matrix[i*cols+j]== *str)){
matrix[i*cols+j]='\0';
ans = dfs(matrix, rows, cols, str+1, i-1, j)
|| dfs(matrix, rows, cols, str+1, i+1, j)
|| dfs(matrix, rows, cols, str+1, i, j-1)
|| dfs(matrix, rows, cols, str+1, i, j+1);
matrix[i*cols+j]=*str;
}
return ans;
}
bool hasPath(char* matrix, int rows, int cols, char* str)
{
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(dfs(matrix, rows, cols, str, i, j)){
return true;
}
}
}
return false;
}
};
编辑于 2016-10-11 22:10:28
回复(3)
//思路：扫一遍矩阵 如果矩阵当前字符等于要查找的第一个字符，则从这个点dfs
// 详见代码注释
char maze[100][100]; //题目给的是char* matrix转换为二维char**maze
int vis[100][100]; //记录是否被访问过
int m,n;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0}; //四个方向
class Solution {
public:
void build(char* matrix,int rows,int cols) //建立二维的矩阵
{
int cnt=0;
for(int i=0;i<rows;++i)
for(int j=0;j<cols;++j)
maze[i][j]=matrix[cnt++];
}
//(x,y)表示当前坐标，des表示要查找的字符串，cnt表示已经匹配上了多少个
//len表示要查找的字符串的长度(好确定递归出口)
bool dfs(int x,int y,char *des,int cnt,int len)
{
if(cnt>=len) //出口
return true;
vis[x][y]=1;
for(int i=0;i<=3;++i)
{
int newx=x+dx[i],newy=y+dy[i];
if(vis[newx][newy]==0&&newx>=0&&newx<m&&newy>=0&&newy<n&&maze[newx][newy]==des[cnt])
{
if(dfs(newx,newy,des,cnt+1,len))
return true;
}
}
return false; //匹配失败
}
bool hasPath(char* matrix, int rows, int cols, char* str)
{
m=rows,n=cols;
build(matrix,rows,cols);
memset(vis,0,sizeof(vis));
for(int i=0;i<rows;++i) //遍历一遍，所以要记得重置vis数组
{
for(int j=0;j<cols;++j)
{
if(maze[i][j]==str[0]&&dfs(i,j,str,1,strlen(str)))
return true;
memset(vis,0,sizeof(vis)); //重置
}
}
return false;
}
};
发表于 2017-06-04 16:22:44
回复(4)
//非递归法。由于一次只能出栈一个，且无法保证下一个的顺序，因此标记必须“随身携带”。
typedef pair<int, int> Pos;
struct State{
Pos p;
int s;
vector<int> vis;
State(Pos pos,int step,vector<int>visit) :
p(pos), s(step), vis(visit) {}
};
class Solution {
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
stack<State>q;
int maxS=strlen(str)-1;
vector<int> v(rows*cols,0);
//every start
for(int x=0;x<rows;x++)
for(int y=0;y<cols;y++){
if(matrix[x*cols+y]==str[0])
{
v[x*cols+y]=true;
q.push(State(Pos(x,y),0,v));
v[x*cols+y]=false;
}
}
while(!q.empty()){
//get
auto t=q.top();q.pop();
auto p=t.p;auto x=p.first,y=p.second; //position
auto s=t.s; //current step
auto vis=t.vis;
//operation
if(s==maxS)return true;
//next
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d],ns=s+1;
if(nx>=0 && nx<rows && ny>=0 && ny<cols &&
ns<=maxS &&
matrix[nx*cols+ny]==str[ns] &&
!vis[nx*cols+ny]){
vis[nx*cols+ny]=true;
q.push(State(Pos(nx,ny),ns,vis));
}
}
}
return false;
}
};
编辑于 2017-08-22 09:34:36
回复(5)
//这道题是典型的深度优先遍历DFS的应用，原二维数组就像是一个迷宫，可以 //上下左右四个方向行走
//我们的二维数组board中每个数都作为起点和给定的字符串做匹配，我们需要
//一个和原二维数组board等大小的visited数组，是bool型的，用来记录当前位置
//是否被访问过。因为题目要求一个cell只能被访问一次。
//如果二维数组的当前字符和目标字符串str对应的字符相等，则对其上下左右四个邻字
//符串分别调用dfs的递归函数，只要有一个返回true，那么就表示找到对应的字符串
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if(str==NULL||rows<=0||cols<=0)
return false;
vector<vector<char>> board(rows, vector<char>(cols));
for(int i = 0; i < rows; ++i){//将matrix装入二维数组board中
for(int j = 0; j < cols; ++j){
board[i][j] = matrix[i*cols + j];
}
}
vector<vector<bool>> visited(rows,vector<bool>(cols, false));
for(int i = 0; i < rows; ++i){
for(int j = 0; j < cols; ++j){
if(dfs(board, str, 0, i, j, visited) == true)
return true;//以矩阵board中的每个字符为起点进行广度优先搜索
//找到一个符合条件的即返回true.
}
}
return false;//遍历完都没找到匹配的路径，返回false
}
private:
bool dfs(vector<vector<char>> board, char* str, int index, int x, int y,
vector<vector<bool>>& visited){
if(index == strlen(str))return true;//搜寻超过路径长度，符合条件，返回true
if((x < 0)||(y < 0)||(x >= board.size()) || (y >= board[0].size()))
return false;//访问越界，终止，返回false
if(visited[x][y]) return false;//之前访问过，剪枝
if(board[x][y] != str[index]) return false;//不相等，剪枝
visited[x][y] = true;
bool ret = dfs(board, str, index+1, x, y-1,visited)|| //上
dfs(board, str, index+1, x, y+1,visited)|| //下
dfs(board, str, index+1, x-1, y,visited)|| //左
dfs(board, str, index+1, x+1, y,visited); //右
visited[x][y] = false;//记得此处改回false，以方便下一次遍历搜索。
return ret;
}
};
编辑于 2019-03-17 22:23:19
回复(0)
function hasPath(matrix, rows, cols, path) {
const flags = new Array(matrix.length).fill(0);
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
const index = i * cols + j;
if (matrix[index] === path[0]) { // 为起点开始
if (hasPathCore(matrix, rows, cols, path, flags, i, j, 0)) return true;
}
}
}
return false;
}
function hasPathCore(matrix, rows, cols, path, flags, i, j, k) {
let index = i * cols + j;
if (i < 0 || j < 0 || i >= rows || j >= cols || flags[index] || path[k] !== matrix[index]) {
return false;
}
if (path.length - 1 === k) {
return true;
}
flags[index] = 1;
if (hasPathCore(matrix, rows, cols, path, flags, i - 1, j, k + 1) ||
hasPathCore(matrix, rows, cols, path, flags, i + 1, j, k + 1) ||
hasPathCore(matrix, rows, cols, path, flags, i, j - 1, k + 1) ||
hasPathCore(matrix, rows, cols, path, flags, i, j + 1, k + 1)
) {
return true;
}
flags[index] = 0;
return false;
}
发表于 2019-10-29 20:33:08
回复(0)
# 基于深度优先遍历的方法
# 与原本的深度遍历不同的地方在于，除了当前路径的节点被标记为DISCOVERED，其他路径上的节点撤销该标记
def hasPath(self, matrix, rows, cols, path):
# write code here
self.discovered = {} # 维护矩阵中的节点是否遍历
self.tar = 0 # 维护要遍历到的path的位置
matrix = list(matrix)
matrix = [matrix[i*cols:i*cols+cols] for i in range(rows)] # 将输入的字符串复原为矩阵
def dfs(x,y): # 深度优先遍历的子函数，只有在遍历刚好结束于path的最后一个字符也相等的时候，返回TRUE
if x<0 or x==rows or y<0 or y==cols: # 如果坐标非法
return False
if (x,y) in self.discovered or matrix[x][y] != path[self.tar]: # 如果坐标已被访问或者坐标与应匹配字符串不同
return False
# 如果坐标合法且匹配正确
if self.tar == len(path) - 1: # 如果已经匹配到了最后一个字符
return True
# 匹配到中间字符，则继续向下遍历
self.discovered[x,y] = 1 # 标记当前坐标，防止重复访问
self.tar += 1 # 向后移动匹配位置
ret = dfs(x-1,y) or dfs(x+1,y) or dfs(x,y-1) or dfs(x,y+1) # 向四个方向进行深度优先遍历，确定匹配最终结果
# 当遍历返回的时候，重置该坐标的访问标志和path的匹配位置
self.discovered.pop((x,y))
self.tar -= 1
return ret
# 依次将每一个单元格作为遍历起点
for i in range(rows):
for j in range(cols):
if dfs(i,j):
return True
return False
发表于 2019-06-22 22:13:03
回复(0)
#python 2.7 递归 时间：34ms 内存：5504k class Solution: def hasPath(self, matrix, rows, cols, path): for i, s in enumerate(matrix): if s==path[0] and self.visit([(i//cols, i%cols)], matrix, rows, cols, path): return True return False def visit(self, ans, matrix, rows, cols, path): if len(ans)==len(path): return True i,j = ans[-1] nex = [(ii,jj) for ii,jj in [(i,j-1),(i,j+1),(i-1,j),(i+1,j)] if 0<= ii <rows and 0<= jj <cols and (ii,jj) not in ans and matrix[ii*cols +jj]==path[len(ans)]] return sum([self.visit(ans+[x], matrix, rows, cols, path) for x in nex])
发表于 2017-12-07 09:41:23
回复(3)
经典回溯题，简单易懂
参考了几个高赞的回答，自己写了一个带注释的，便于自己理解
思路：
1.回溯经典题
2.本题首先要解决是如何理解这个输入，按道理来说是矩阵，但是给了一维数组
3.一开始也没有头绪，但是我们可以看到输入同时还给了行和列
4.但是一维数组为什么要给行和列？很明显是要我们自己构建二维数组
5.比如输入的是，martix={a,b,c,e,s,f,c,s,a,d,e,e},rows=3,cols=4
6.那么构建的二维数组就是：{{a,b,c,e},{s,f,c,s},{a,d,e,e}}
7.理解了这一点，现在有两种做法，一是我们自己创建这个二维数组
8.或者我们就使用原来的一维数组，通过公式index=i*cols+j，来计算元素的下标
9.我们知道回溯大部分题都会使用递归来解决问题
10.那首先找到递归的结束条件
11.每次递归可以走四个方向，每次都需判断是否等于要找的字符，且规定不能使用重复字符
12.递归的结束条件就是，不能越界，要满足字符相等，不能重复使用
13.然后找递归公式，很显然，就是分别走四个方向，每个方向都是一次递归 public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
//鲁棒
if (matrix.length < str.length || rows > matrix.length || cols > matrix.length) {
return false;
}
//构建一个和原一维数组大小相同的boolean数组，记录字符是否被使用过
boolean[] flag = new boolean[matrix.length];
//设置一个字符匹配数
int k = 0;
//间接的构建二维数组
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
//找到一组直接返回true
if (pathHelper(matrix, i, j, rows, cols, str, flag, k)) {
return true;
}
}
}
return false;
}
/**
* 通过不断的递归来寻路
*/
public static boolean pathHelper(char[] matrix, int i, int j, int rows, int cols
, char[] str, boolean[] flag, int k) {
//通过公式计算出二维数组在一维数组中的位置
int index = i * cols + j;
//1.递归结束条件
if (i < 0 || j < 0 || i >= rows || j >= cols || matrix[index] != str[k] || flag[index]) {
return false;
}
//如果刚好匹配完的话，直接返回true
if (k == str.length - 1) {
return true;
}
//开始回溯之前将本次回溯的字符标记位置为true，表示已经使用过了
flag[index] = true;
//开始回溯，上下左右分别回溯
if (pathHelper(matrix, i - 1, j, rows, cols, str, flag, k + 1) ||
pathHelper(matrix, i + 1, j, rows, cols, str, flag, k + 1) ||
pathHelper(matrix, i, j - 1, rows, cols, str, flag, k + 1) ||
pathHelper(matrix, i, j + 1, rows, cols, str, flag, k + 1)) {
return true;
}
//四个方向都没找到的话，说明当前字符不行,我们往回走，恢复flag
flag[index] = false;
return false;
}
编辑于 2020-04-21 16:25:21
回复(0)
回溯法，提前构造矩阵，参考剑指offer代码
# -*- coding:utf-8 -*-
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
if rows == 0 or cols == 0:
return False
self.build_matrix(matrix, rows, cols)
for i in range(rows):
for j in range(cols):
if self.find(i, j, 0, rows, cols, path):
return True
return False
def find(self, i, j, l, rows, cols, path):
if l == len(path):
return True
if i < 0 or i >= rows or j < 0 or j >= cols or self.flag[i][j] or self.new_matrix[i][j] != path[l]:
return False
self.flag[i][j] = 1
for n in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
if self.find(i+n[0], j+n[1], l+1, rows, cols, path):
return True
self.flag[i][j] = 0
return False
def build_matrix(self, matrix, rows, cols):
self.flag = []
self.new_matrix = []
for i in range(rows):
self.flag.append([0]*cols)
self.new_matrix.append(list(matrix[i*cols:cols+i*cols]))
# s = Solution()
# print(s.hasPath("ABCESFCSADEE", 3, 4, "ABCCED"))
编辑于 2019-03-11 17:22:36
回复(1)
// dfs遍历。。。
class Solution {
public:
bool dfs(char *matrix,char *str,int *visited,int rows,int cols,int r,int c,int l,int *stop){
if(*stop==1)return true;
int r1,c1,p;
int dr[]={-1,0,1,0};
int dc[]={0,1,0,-1};
p=r*cols+c;
visited[p]=1;
if(str[l+1]=='\0'){
*stop=1;
return true;
}
for(int i=0;i<4;i++){
r1=r+dr[i];
c1=c+dc[i];
if(r1<0||r1>=rows)continue;
if(c1<0||c1>=cols)continue;
p=r1*cols+c1;
if(!visited[p]&&str[l+1]==matrix[p]){
if(dfs(matrix,str,visited,rows,cols,r1,c1,l+1,stop))
return true;
}
}
return false;
}
bool hasPath(char* matrix, int rows, int cols, char* str)
{
int visited[rows*cols],p,stop;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
p=i*cols+j;
if(matrix[p]==str[0]){
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
p=i*cols+j;
visited[p]=0;
}
}
stop=0;
if(dfs(matrix,str,visited,rows,cols,i,j,0,&stop)){return true;}
}
}
}
return false;
}
};
发表于 2017-08-28 15:02:44
回复(0)
//回溯法，写了两种，注意flag矩阵的处理
//第一种
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str) {
bool res = 0;
for (int i = 0;i<rows;++i) {
for (int j = 0;j<cols;++j) {
//bool *flag = (bool *)calloc(rows*cols, 1);
//vector<bool> flag(rows*cols,0);
bool *flag=new bool[rows*cols];
memset(flag,0,rows*cols);
res = dfs(matrix, rows, cols, i, j, flag, str);
if (res == true)
return res;
}
}
return res;
}
bool dfs(char* matrix, int rows, int cols, int i, int j, bool* flag, char* str) {
if (*(flag+i*cols + j) == 1 || (*(flag+i*cols + j) == 0 && *(matrix + i*cols + j) != *str))
return false;
else {
*(flag+i*cols + j) = 1;
if (*(str+1) == '\0')
return true;
bool res1 = 0, res2 = 0, res3 = 0, res4 = 0;
//左
if (j > 0 && j < cols)
res1 = dfs(matrix, rows, cols, i, j - 1, flag, str + 1);
//右
if (j >= 0 && j<cols - 1)
res2 = dfs(matrix, rows, cols, i, j + 1, flag, str+1);
//上
if (i>0 && i<rows)
res3 = dfs(matrix, rows, cols, i - 1, j, flag, str+1);
//下
if (i >= 0 && i<rows - 1)
res4 = dfs(matrix, rows, cols, i + 1, j, flag, str+1);
if(res1 || res2 || res3 || res4==0)
*(flag+i*cols + j)=0;
return res1 || res2 || res3 || res4;
}
}
};
//第二种，参照剑指offer简化了一下
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str) {
bool res = 0;
bool *flag=new bool[rows*cols];
memset(flag,0,rows*cols);
for (int i = 0;i<rows;++i) {
for (int j = 0;j<cols;++j) {
//bool *flag = (bool *)calloc(rows*cols, 1);
res = dfs(matrix, rows, cols, i, j, flag, str);//1
if (res == true)
return res;
}
}
delete[] flag;
return res;
}
bool dfs(char* matrix, int rows, int cols, int i, int j, bool* flag, char* str) {
if (*str == '\0')
return true;
if(i<0||i>=rows||j<0||j>=cols)
return false;
if (*(flag+i*cols + j) == 1 || (*(flag+i*cols + j) == 0 && *(matrix + i*cols + j) != *str))
return false;
else {
*(flag+i*cols + j) = 1;
bool res=dfs(matrix, rows, cols, i, j - 1, flag, str + 1)//左
||dfs(matrix, rows, cols, i, j + 1, flag, str+1)//右
||dfs(matrix, rows, cols, i - 1, j, flag, str+1)//上
||dfs(matrix, rows, cols, i + 1, j, flag, str+1);//下
if(res==0)
*(flag+i*cols + j)=0;//这样从1处开始进入的DFS即使没找到路径，但是flag最后全部置为0
return res;
}
}
};
发表于 2017-06-28 22:17:58
回复(0)
思路
毋庸置疑最先想到回溯法。
说一个空间复杂度O(1)的。
走过的地块标为 ' ' 等不会用到的字符即可。
时间复杂度最差也不会到O(n2)，没时间没能力算具体多少，总之实际上不太多。
类似的问题如：填海造陆，离陆最远等dfs,bfs问题。
多说两句说一下思路吧。数组存储的矩阵的任意一点(i,j)在数组中的位置k=i*cols+j
（btw，k在矩阵一点的位置(k/cols, k%cols)）。
通过递归回溯，遍历数组，找从一点开始上下左右走且不重复的情况下，走出str路径的情况即可。
代码
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
for (int i = 0; i < matrix.length; i++) {
if (findPath(matrix, cols, i, str, 0)) return true;
}
return false;
}
public boolean findPath(char[] matrix, int cols, int k, char[] str, int c) {
if (c >= str.length) return true;
if (k < 0 || k >= matrix.length || matrix[k] != str[c]) return false;
int i = k / cols;
int j = k % cols;
char tmp = matrix[k];
matrix[k] = ' ';
if (findPath(matrix, cols, (i-1)*cols+j, str, c+1) ||
findPath(matrix, cols, (i+1)*cols+j, str, c+1) ||
findPath(matrix, cols, i*cols+j-1, str, c+1) ||
findPath(matrix, cols, i*cols+j+1, str, c+1))
return true;
matrix[k] = tmp;
return false;
}
发表于 2021-02-22 20:46:11
回复(0)
问题信息
难度：
672条回答
1454收藏
113143浏览
通过挑战的用户
-
2023-03-07 09:36:39 -
2023-02-27 02:46:12
-
2022-09-13 21:57:01
-
2022-09-10 15:23:48 -
2022-09-08 12:00:40
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
分析：回溯算法 这是一个可以用回朔法解决的典型题。首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的 第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。 重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。 由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个 字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。 由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。 当矩阵中坐标为（row,col）的 格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符 如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。 一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置 class Solution { public: bool hasPath(char* matrix, int rows, int cols, char* str) { if(str==NULL||rows<=0||cols<=0) return false; bool *isOk=new bool[rows*cols](); for(int i=0;i<rows;i++) { for(int j=0;j<cols;j++) if(isHsaPath(matrix,rows,cols,str,isOk,i,j)) return true; } return false; } bool isHsaPath(char *matrix,int rows,int cols,char *str,bool *isOk,int curx,int cury) { if(*str=='\0') return true; if(cury==cols) { curx++; cury=0; } if(cury==-1) { curx--; cury=cols-1; } if(curx<0||curx>=rows) return false; if(isOk[curx*cols+cury]||*str!=matrix[curx*cols+cury]) return false; isOk[curx*cols+cury]=true; bool sign=isHsaPath(matrix,rows,cols,str+1,isOk,curx-1,cury) ||isHsaPath(matrix,rows,cols,str+1,isOk,curx+1,cury) ||isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury-1) ||isHsaPath(matrix,rows,cols,str+1,isOk,curx,cury+1); isOk[curx*cols+cury]=false; return sign; } };