AcWing 23. 矩阵中的路径

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 23. 矩阵中的路径原题链接中等

作者：

yxc , 2019-01-06 00:50:21 , 所有人可见 , 阅读 14423

75

31

算法

(DFS) $O(n^23^k)$

在深度优先搜索中，最重要的就是考虑好搜索顺序。

我们先枚举单词的起点，然后依次枚举单词的每个字母。
过程中需要将已经使用过的字母改成一个特殊字母，以避免重复使用字符。

时间复杂度分析：单词起点一共有 $n^2$ 个，单词的每个字母一共有上下左右四个方向可以选择，但由于不能走回头路，所以除了单词首字母外，仅有三种选择。所以总时间复杂度是 $O(n^23^k)$。

C++ 代码

class Solution {
public:
    bool hasPath(vector<vector<char>>& matrix, string str) {
        for (int i = 0; i < matrix.size(); i ++ )
            for (int j = 0; j < matrix[i].size(); j ++ )
                if (dfs(matrix, str, 0, i, j))
                    return true;
        return false;
    }

    bool dfs(vector<vector<char>> &matrix, string &str, int u, int x, int y) {
        if (matrix[x][y] != str[u]) return false;
        if (u == str.size() - 1) return true;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        char t = matrix[x][y];
        matrix[x][y] = '*';
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()) {
                if (dfs(matrix, str, u + 1, a, b)) return true;
            }
        }
        matrix[x][y] = t;
        return false;
    }
};

87 评论

liuhankang 2022-08-23 18:37

## 想不到

我中了 2022-03-08 10:57

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};这一句是啥意思呀

小南新 2022-03-16 10:22

代表上下左右移动，dx的-1代表向左移动，1代表向右移动。dy的-1代表向上移动，1代表向下移动

acwing_4785 10个月前

class Solution {
public:
    bool visited[901][901];
    int pos[4][2] = {
        { -1 , 0 } , { 0 , 1 } , { 1 , 0 } , { 0 , -1 }
    };
    bool hasPath(vector<vector<char>>& matrix, string &str) {
        if(matrix.empty()) return false; 
        memset(visited , 0 , sizeof(visited));
        for(int i = 0 ;i < matrix.size() ; i ++)
            for(int j = 0 ;j < matrix[i].size() ; j ++)
                if(matrix[i][j] == str[0]) {
                    visited[i][j] = 1;
                    if(find_path(matrix , str , 1 , i , j)) return true;
                    visited[i][j] = 0;
                }
        return false;
    }

    bool find_path(vector<vector<char>>& matrix , string& str ,int now , int x , int y) {
        if(now == str.size()) return true;
        for(int i = 0 ;i < 4 ; i ++) {
            int newx = x + pos[i][0] , newy = y + pos[i][1];
            if(is_feasible(newx , newy , matrix) && matrix[newx][newy] == str[now]){
                visited[newx][newy] = 1;
                if(find_path(matrix , str , now + 1 , newx , newy)) return true;
                visited[newx][newy] = 0;
            }
        }
        return false;
    }

    // bool find_path(vector<vector<char>>& matrix , string& str, int now ,int x,  int y) {
    //     if(now == str.size() - 1) return true;
    //     bool flag = false;
    //     for(int i =0 ;i < 4 ; i ++) {
    //         int newx = x + pos[i][0] , newy = y + pos[i][1];
    //         if(is_feasible(newx , newy , matrix) && matrix[newx][newy] == str[now + 1]) {
    //             visited[newx][newy] = 1;
    //             flag = find_path(matrix , str , now + 1 , newx , newy);
    //             visited[newx][newy] = 0;
    //             if(flag) return true;
    //         }
    //     }
    //     return false;
    // }

    bool is_feasible(int x,  int y , vector<vector<char>>& matrix) {
        return x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size() && !visited[x][y];
    }
};

没想到用特殊字符替代的这种方法，学到了，习惯性开visited数组浪费了好多空间。

时来天地皆同力 2023-05-29 16:23

class Solution {
public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    bool st[1000][1000];
    int n, m;
    bool dfs(int x, int y, int u, string& str, vector<vector<char>>& matrix) {

        // 错误写法
        if (u == str.size()) return true;
        if (matrix[x][y] != str[u]) return false;  

        // 正确写法
        // if (matrix[x][y] != str[u]) return false;  
        // if (u == str.size() - 1) return true;

        st[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || st[nx][ny]) continue;
            if (dfs(nx, ny, u + 1, str, matrix)) return true;
        }
        st[x][y] = false;
        return false;
    }

    bool hasPath(vector<vector<char>>& matrix, string &str) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;
        n = matrix.size(), m = matrix[0].size();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                if (dfs(i, j, 0, str, matrix)) return true;
            }
        }
        return false;
    }
};

请问换成错误代码那两行之后错在哪了？过了15个样例

wqqq 2023-08-17 09:49

你好，我的理解是这个例子 str=a martix=[a]

第一步成功了，但是在继续dfs的时候是不能继续dfs的，因为 if (nx < 0 || nx >= n || ny < 0 || ny >= m || st[nx][ny]) continue; 下标全都越界，进入 continue ,没法进入预计的dfs（1）

陨月之殇 2023-04-24 12:56

请问大佬们，这个哪里出错了只不过是用x=x+dx[i],y=y+dy[i];就出错了，是产生歧义了吗，还是这个会改变x的值，求大佬解答Orz
class Solution {
public:
vector[HTML_REMOVED]path;
bool hasPath(vector[HTML_REMOVED]>& matrix, string &str) {
for( int i=0;i[HTML_REMOVED]>& matrix, string &str,int x,int y,int u)
{
if(matrix[x][y]!=str[u]) return false;
if(u==str.size()-1) return true;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
char ch=matrix[x][y];
matrix[x][y]=’*’;
for(int i=0;i<4;i++)
{
x=x+dx[i];y=y+dy[i];
if(x>=0&&x[HTML_REMOVED]=0&&y<matrix[x].size())
{
if(dfs(matrix,str,x,y,u+1)) return true;
}
}
matrix[x][y]=ch;
return false;
}
};

19933210296 2023-11-19 16:25

改变x、y的值了，恢复现场的时候会改变matrix其他位置的值

懂王就得不懂装懂 2022-10-07 08:31

大佬们，请问这个是哪里出错呢
class Solution {
public:
int curi,curj;
int dpi[4]={0,0,1,-1};
int dpj[4]={1,-1,0,0};
int a[907][907];
bool hasPath(vector[HTML_REMOVED]>& matrix, string &str) {
memset(a,0,sizeof(a));
int n=matrix.size();
if(n==0)
return false;
int m=matrix[0].size();
int i,j;
int p=0;
for(i=0;i[HTML_REMOVED]> &m,string &s,int sum)
{
if(sum==s.size())
return true;
if(curi<0||curj<0||curi>=m.size()||curj>=m[0].size()||(m[curi][curj]!=s[sum]&&sum[HTML_REMOVED]=0&&curj>=0&&curi<m.size()&&curj<m[0].size()&&m[curi][curj]==s[sum]&&sum<s.size())
return dfs(curi+dpi[0],curj+dpj[0],m,s,sum)||dfs(curi+dpi[1],curj+dpj[1],m,s,sum)||dfs(curi+dpi[2],curj+dpj[2],m,s,sum)||dfs(curi+dpi[3],curj+dpj[3],m,s,sum);
}
};

遇城 2022-04-23 23:17

想知道n²3^k那个k是怎么打上去的TAT

天郁闷 2022-07-31 08:52

$O(n^23^k)$

天郁闷 2022-07-31 08:53

$(n^23^k)$

遇城 2022-08-04 17:09 回复了天郁闷的评论

哇谢谢!

我中了 2022-03-08 14:18

matrix[x][y] = t;这一步感觉没啥用吧

LixingZZZ 2022-03-09 18:33

恢复现场吧，这是传的引用，matrix的值被修改了，如果不恢复的话不然下一次dfs的时候就会有问题

天郁闷 2022-07-31 08:54

恢复现场，保证在搜索一条路径时一个字母只用一次

重新学习 2021-09-03 14:10

这个题的思路和蛇形矩阵好像啊

归零_3 2021-05-05 21:31

这个为什么会段错误呢qaq

int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool dfs(vector<vector<char>>v,vector<vector<bool>>&exist,string s,string str,int x,int y){
    s+=v[x][y];
    if(s==str)  return true;
    if(s.length()>str.length()) return false;
    if(x<0||x>=v.size()||y<0||y>=v[0].size())// 循环里再判断出界
        return false;
    exist[x][y]=true;
    for(int i=0;i<4;i++){
        int dx=x+dir[i][0],dy=y+dir[i][1];
        if(dx>=0&&dx<v.size()&&dy>=0&&dy<v[0].size()&&!exist[dx][dy])
            if(dfs(v,exist,s,str,dx,dy))
                return true;
    }
    exist[x][y]=false;
    return false;

}
//没有指定一定从原点开始
bool hasPath(vector<vector<char>>& matrix, string &str) {
    if(matrix[0].size()==0||matrix.size()==0) return false;
    int m=matrix.size(),n=matrix[0].size();
    vector<vector<bool>>exist(m,vector<bool>(n,false));

    for(int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
            if (matrix[i][j] == str[0]) {
                bool a=dfs(matrix,exist,"",str,i,j);
                if (a){
                    return true;
                }
            }
        }
    }
    return false;
}

空山1新雨 2022-02-23 22:52

错误数据是二维数组为空

if(matrix[0].size()==0||matrix.size()==0) return false;

这句会先执行matrix[0].size()==0,对空数组取下标为0的元素就越界了。可以改为

if(matrix.size()==0||matrix[0].size()==0) return false;

第一个条件为true就不会执行第二个语句了

小华老师 2021-04-24 15:11

666

lii_01 2021-04-08 11:36

if (matrix[x][y] != str[u]) return false; if (u == str.size() - 1) return true;
请问有大佬能解释一下这两行是什么意思吗?

Nemo_7 2021-04-09 23:40

第一个if是指当前字符串不匹配直接返回false
第二个if是指当第当前字符匹配且当前为最后一个字符时，直接返回true

lii_01 2021-04-12 09:45 回复了 Nemo_7 的评论

明白了~谢谢！

skypemifen 2021-06-23 17:21 回复了 Nemo_7 的评论

谢谢！

捡到一束光 2021-11-01 17:14 回复了 Nemo_7 的评论

而且这两行顺序还不能换

半醒的狐狸 2022-01-03 19:57 回复了捡到一束光的评论

避免最后一个u不同的情况

Critic 2022-02-23 09:11 回复了 Nemo_7 的评论

感谢

water-lover 9个月前回复了捡到一束光的评论

大佬，为什么这两行的顺序不能换呢？

上下求索 2021-02-03 15:40

我 y 总写的代码好骚啊！

coorch 2020-09-20 20:51

y总，用来保存matrix[x][y]值的临时变量t是不是可以不用定义？因为程序进行到了这里，matrix[x][y]==str[u]是成立的，还原matrix[x][y]的时候直接用str[u]是不是就可以啦

yxc 2020-10-09 15:47

可以的。

曹亚洲 2020-09-05 16:27

定义的变量好多，看混淆了都

yxc 2020-10-09 15:47

这题变量不多呀hh

木香 2020-07-21 16:41

您好，请问您一下为什么这个方法在LeetCode上运行，会显示当输入是[[“a”]]”ab” 时，会输出true

木香 2020-07-23 11:05

已找到问题所在，谢谢啦~

yxc 2020-08-17 13:18 回复了木香的评论

好滴

哈哈哈hh 2020-06-15 16:54

为什么这一种写法是 cur.size() == index, 而上面这种是cur.size() - 1 == index

bool backtrack(vector<vector<char>> &board, int row, int col, 
                   const string &word, int idx) {
            if(word.size() == idx)
                return true;
        if(row < 0 || row >= board.size() ||
          col < 0 || col >= board[0].size())
            return false;
        if(word[idx] != board[row][col])
            return false;
     board[row][col] = '*';
            if (backtrack(board, row - 1, col, word, idx + 1) || 
            backtrack(board, row + 1, col, word, idx + 1) ||
            backtrack(board, row, col - 1, word, idx + 1) || 
            backtrack(board, row, col + 1, word, idx + 1)) 
            return true;

        board[row][col] = word[idx];
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) 
            return word.empty();
        for (int row = 0; row < board.size(); ++row) {
            for (int col = 0; col < board[0].size(); ++col) {
                if (backtrack(board, row, col, word, 0)) return true;
            }
        }

        return false;
    }

yxc 2020-07-02 15:00

都是可以的。

dys 2020-05-11 17:15

y总，貌似这两句交换顺序，就通过不了了

if(matrix[x][y]!=str[u]) return false; 
        if(u==str.size()-1) return true;

yxc 2020-05-13 17:27

最后一个位置没有判断是否相同就直接返回true，肯定不对啊。

捡到一束光 2021-11-01 17:15 回复了 yxc 的评论

而且第一行u一定不会越界

xnuohz 2020-03-01 21:26

if (matrix[x][y] != str[n]) return false;
if (n == str.size() - 1) return true;

yls，为什么上面的可以过，下面的就错了呢？

if (n == str.size()) return true;
if (matrix[x][y] != str[n]) return false;

yxc 2020-03-03 09:07

if (n == str.size())和if (n == str.size() - 1)不等价。另外调试代码要学会用printf大法，这样学起来会快一些。

TwoSum 2020-03-16 18:40 回复了 yxc 的评论

请问OJ上也能用printf吗？

yxc 2020-03-25 02:34 回复了 TwoSum 的评论

能用，没问题。

喜欢吃鱼 2020-04-08 12:38 回复了 yxc 的评论

但是在下面那种方式中，运行到if (n == str.size())时，所有的字符都已匹配完，所以应该也没问题才对啊，这里不太明白。。

喜欢吃鱼 2020-04-08 12:43 回复了喜欢吃鱼的评论

是不是因为这样：
虽然n个字符已经匹配完成，但没有return退出当前函数的话，会继续执行下面的代码，那么在当前函数里，会以n为起点继续去搜索，所以出了问题。

yxc 2020-04-20 01:55 回复了喜欢吃鱼的评论

当输入是[["a"]], "a"时下面的写法会返回false。

Oenomaus 2020-04-27 14:02

下面的写法，如果输入是单字符，就进不去for循环然后直接返回false

zaiwuhan 2020-04-27 22:46 回复了 Oenomaus 的评论

能进去for循环，但是进不去for循环里边的第一个if判断，因为单个字符无论向哪个方向移动，都会超出边界，所以四个方向搜索完以后，最后输出false

Oenomaus 2020-04-28 10:05 回复了 zaiwuhan 的评论

嗯

yxc 2020-05-13 17:23 回复了 zaiwuhan 的评论

对滴。

罗小呆 2022-02-18 11:34 回复了 zaiwuhan 的评论

虽然能理解，但还是让人心情失落，又不能说玄学

鱼尾 2020-02-08 08:15

如果测试数据为[[“A”]] “A”,按照上述程序会输出false啊，因为进不去for循环中的if语句

for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()) {
                if (dfs(matrix, str, u + 1, a, b)) return true;
            }
        }

yxc 2020-02-14 19:49

我运行了一遍，会输出true。

zly 2020-04-16 14:44

它应该是在if(u == str.length() - 1) return true;时就返回了true的

App 内打开