DFSArray

发表于 分类于

题目描述[原题描述][https://www.acwing.com/problem/content/21/]

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

  • 输入的路径不为空；
  • 所有出现的字符均为大写英文字母；

样例

1
2
3
4
5
6
7
8
9
10
matrix=
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]

str="BCCE" , return "true" 

str="ASAE" , return "false"

算法描述

  • 首先遍历入口，及遍历矩阵
  • 写dfs函数，定义好出口，当n==字符串长度-1时返回true
  • 细节处理，移动前m[x][y]='*',移动完需要恢复

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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[0].size();j++){
                if(dfs(matrix,str,0,i,j))
                    return true;
            }
        }
        return false;
    }
    
    bool dfs(vector<vector<char>>&m,string& str,int u,int x,int y){
        if(m[x][y]!=str[u])return false;
        if(u == str.size()-1)return true;
        char t = m[x][y];
        int dx[]={-1,0,1,0};
        int dy[]={0,1,0,-1};
        m[x][y] = '#';
        for(int i=0;i<4;i++){
            int a = x+dx[i],b = y+dy[i];
            if(a>=0&&a<m.size()&&b>=0&&b<m[0].size()){
                if(dfs(m,str,u+1,a,b))return true;
            }
        }
        m[x][y] = t;
        return false;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    String s = new String();
    public boolean hasPath(char[][] matrix, String str) {
        if(matrix.length==0||matrix[0].length==0)return false;
        s=str;
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(dfs(matrix,0,i,j))return true;
            }
        }
        return false;
    }
    
    boolean dfs(char[][] matrix,int n,int x,int y){
        if(matrix[x][y]!=s.charAt(n))return false;
        if(s.length()-1==n)return true;
        char c = matrix[x][y];
        matrix[x][y]='*';
        int dx[]={0,-1,0,1},dy[]={1,0,-1,0};
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<matrix.length&&b>=0&&b<matrix[0].length){
                if(dfs(matrix,n+1,a,b))return true;
            }
        }
        matrix[x][y]=c;
        return false;
    }
}