【回溯专题】剑指 Offer 12. 矩阵中的路径-跟着帅地玩副业，开拓第二曲线PlayOffer

神经蛙普通 2024年4月2日上午12:03

class Solution {
public:
bool wordPuzzle(vector<vector>& grid, string target) {
int n = grid.size();
int m = grid[0].size();
int l = target.size();

    vector<vector<bool>> visited(n, vector<bool>(m, false));

    function<bool(int, int, int)> dfs = [&](int i, int j, int k) -> bool {
        if (i < 0 || i >= n || j < 0 || j >= m || visited[i][j] || grid[i][j] != target[k]) {
            return false;
        }

        if (k == l - 1) {
            return true;
        }

        visited[i][j] = true;
        bool res = dfs(i, j + 1, k + 1) || dfs(i + 1, j, k + 1) || dfs(i, j - 1, k + 1) || dfs(i - 1, j, k + 1);
        visited[i][j] = false;

        return res;
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (dfs(i, j, 0)) {
                return true;
            }
        }
    }

    return false;
}

};
打卡

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月30日下午9:13

打卡

class Solution {
public:
    bool wordPuzzle(vector<vector<char>>& grid, string target) {
        rows = grid.size(), cols = grid[0].size();

        // 先找到单词的入口，即target的首字母
        for(int i = 0; i < rows; ++i) {
            for(int j = 0; j < cols; ++j) {
                if(dfs(grid, target, i, j, 0)) 
                    return true;
            }
        }
        return false;
    }
private:
    // i,j是当前遍历到的矩阵字符，k是下次要查找的target中的位置的字母
    bool dfs(vector<vector<char>>& grid, string target, int i, int j, int k) {
        // 终止：越界/ 当前遍历的grid中的位置的单词不是这次要找的
        if(i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != target[k]) return false;
        if(k == target.length() - 1) return true; // 已经顺利遍历到即找到target中最后一个单词
        grid[i][j] = '\0'; // 标记当前字符已经被访问过了
        // 递归搜索四个方向
        bool res = dfs(grid, target,i + 1, j, k + 1) || dfs(grid, target, i, j + 1, k + 1)
                    || dfs(grid, target, i - 1, j, k + 1) || dfs(grid, target, i, j - 1, k + 1);
        grid[i][j] = target[k]; // 之前标记已经访问过了，这里相当于回溯
        return res;
    }

private:
    int rows, cols;
};

0 赞同 0 条回复

言之命至普通 2024年3月30日上午10:15

class Solution {
    int n;
    int m;
    int len;
    boolean[][] visited;//是否拜访过
    public boolean exist(char[][] board, String word) {
        this.n = board.length;
        this.m = board[0].length;
        this.len = word.length();
        visited = new boolean[n][m];

        for(int i = 0; i < n; i++){//遍历搜索
            for(int j = 0; j < m; j++){
                if(dsf(board, i, j, word, 0)){
                    return true;
                }
            }
        }

        return false;
    }
    boolean dsf(char[][] board, int i, int j, String word, int k){
        // 判断是否越界，已经访问过或者不匹配
        if(i < 0 || i >= n || j < 0 || j >= m || board[i][j] != word.charAt(k)){
            return false;
        }

        if(k == len - 1){//匹配到最后一个字符
            return true;
        }
        //visited[i][j] = true;
        board[i][j] = '\n';//也可以不用 visited[i][j]，赋一个特殊值
        // 四个方向都搜索一下，右，下，左，上的 顺序
        boolean res = dsf(board, i, j + 1, word, k + 1) ||
                      dsf(board, i + 1, j, word, k + 1) ||
                      dsf(board, i, j - 1, word, k + 1) ||
                      dsf(board, i - 1, j, word, k + 1);
   //visited[i][j] = false;
        board[i][j] = word.charAt(k);//赋回原来的值
        return res;
        // 时间复杂度：mn * 3^len
        //空间：n*n
    }
}

时间复杂度：mn * 3^len
空间：n*n

0 赞同 0 条回复

紫芝普通 2024年3月29日下午5:35

思路：dfs

“`c++
class Solution {
public:
bool wordPuzzle(vector>& grid, string target) {
for (int i=0; i>& grid, string target, int idx, int row, int col) {
if (idx == target.size()) return true;
if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] != target[idx]) return false;
grid[row][col] = ‘\0’;
if (dfs(grid, target, idx+1, row-1, col) || dfs(grid, target, idx+1, row+1, col) || dfs(grid, target, idx+1, row, col-1) || dfs(grid, target, idx+1, row, col+1)) return true;
grid[row][col] = target[idx];
return false;
}
};
“`

0 赞同 0 条回复

方铎码农普通 2024年3月29日上午11:32

class Solution {
    public boolean wordPuzzle(char[][] grid, String target) {
        char[] words = target.toCharArray();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(dfs(grid, words, i, j, 0)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] grid, char[] target, int i, int j, int k){
        if(i >= grid.length || i < 0 || j >= grid[0].length || j < 0 || grid[i][j] != target[k])
            return false;   //返回false使得函数回溯
        if(k == target.length - 1) 
            return true;
        // 使用空字符做标记是为了防止标记字符与矩阵原有字符重复
        grid[i][j] = '\0';
        //上下左右遍历，遍历都报错则回溯报false
        boolean res = dfs(grid,target,i-1,j,k+1) || dfs(grid,target,i,j-1,k+1) ||dfs(grid,target,i+1,j,k+1) || dfs(grid,target,i,j+1,k+1);
        grid[i][j] = target[k];
        return res;
    }
}

0 赞同 0 条回复

heathhou 普通 2024年3月28日下午11:22

class Solution {
public:
    bool wordPuzzle(vector<vector<char>>& grid, string target) {
        n = grid.size();
        m = grid[0].size();
        l = target.size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));;

        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(dfs(grid, i, j, target, 0, visited)){
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& grid, int i, int j,string& target, int k, vector<vector<bool>>& visited){
        if(i < 0 || i >= n || j < 0 || j >= m || visited[i][j] == true || grid[i][j] != target[k]){
            return false;
        }

        if(k == l - 1){
            return true;
        }

        visited[i][j] = true;
        bool res =  dfs(grid, i, j + 1, target, k + 1, visited) ||
                    dfs(grid, i + 1, j, target, k + 1, visited) ||
                    dfs(grid, i, j - 1, target, k + 1, visited) ||
                    dfs(grid, i - 1, j, target, k + 1, visited);
        visited[i][j] = false;
        return res;
    }
private:
    int n;
    int m;
    int l;

};

时间复杂度：O(nm3^len)
空间复杂度: O(n * m)

0 赞同 0 条回复

机电皮怪永久会员 2024年3月28日下午10:48

时间复杂度O(MN),空间复杂度O(MN)

“`C++
class Solution {
public:
bool wordPuzzle(vector>& grid, string target) {
int n = grid.size();
int m = grid[0].size();
int l = target.size();
vector> visit(n, vector(m, false));

    function<bool(int, int, int)> dfs = [&](int i, int j, int k) -> bool
    {
        if( i < 0 || i >= n || j < 0 || j >= m || visit[i][j] || grid[i][j] != target[k])
        {
            return false;
        }

        if(k == l - 1)
        {
            return true;
        }

        visit[i][j] = true;
        bool res = dfs(i + 1, j, k + 1) || dfs(i, j + 1, k + 1) || dfs(i - 1, j, k + 1) || dfs(i, j - 1, k + 1);
        visit[i][j] = false;

        return res;
    };

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(dfs(i, j, 0))
            {
                return true;
            }
        }
    }

    return false;
}

};

“`

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月28日下午9:32

class Solution {

    int n;//grid 行数
    int m; // 列数
    int len;// target长度
    boolean[][] visited;

    public boolean wordPuzzle(char[][] grid, String target) {
        this.n=grid.length;
        this.m=grid[0].length;
        this.len=target.length();

        visited = new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(dfs(grid,i,j,target,0)){
                    return true;
                }
            }
        }

        return false;

    }

    boolean dfs(char[][] grid, int i,int j,String target,int k){
        if(i<0 || i>=n || j<0 || j>=m || grid[i][j]!=target.charAt(k) || visited[i][j]==true){
            return false;
        }
        if(k==len-1) return true;

        visited[i][j]=true;
        // grid[i][j] = '\n';
        boolean res = dfs(grid,i+1,j,target,k+1) ||
                        dfs(grid,i,j+1,target,k+1) ||
                        dfs(grid,i-1,j,target,k+1) ||
                        dfs(grid,i,j-1,target,k+1);
        visited[i][j]=false;
        // grid[i][j] = target.charAt(k);

        return res;
    }
}

回溯体现在对visited[][]的修改

0 赞同 0 条回复

Jimmy 普通 2024年3月28日下午8:12

深度优先搜索

class Solution {
public:
    int n;
    int m;
    int len;
    vector<vector<bool>> visited;


    bool wordPuzzle(vector<vector<char>>& grid, string target) {
        n = grid.size();
        m = grid[0].size();
        len = target.size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(dfs(grid,i,j,target,0,visited))
                {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& grid, int i,int j,string target,int k,vector<vector<bool>>& visited)
    {
        if(i<0 || i>=n || j<0 || j>=m || grid[i][j] != target[k] || visited[i][j])
        {
            return false;
        }
        if(k == len-1)
        {
            return true;
        }

        visited[i][j] = true;
        bool res = dfs(grid,i,j+1,target,k+1,visited) || dfs(grid,i+1,j,target,k+1,visited) || dfs(grid,i,j-1,target,k+1,visited) || dfs(grid,i-1,j,target,k+1,visited);
        visited[i][j] = false;
        return res;
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年3月28日上午1:01

class Solution {

public boolean wordPuzzle(char[][] grid, String target) {
    for(int i = 0; i < grid.length;i++)
        for(int j = 0; j < grid[0].length;j++){
            if(canGo(grid,target,0,i,j))                    
                return true;
        }
    return false;
}
private boolean canGo(char[][] grid, String target,int loc,int x,int y) {
    if(loc == target.length())
        return true;
    if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length  || grid[x][y] != target.charAt(loc))
        return false;
    else{
        char temp = grid[x][y];
        grid[x][y]=' ';
        boolean signal;
        signal = canGo(grid,target,loc+1,x+1,y) || canGo(grid,target,loc+1,x-1,y) || canGo(grid,target,loc+1,x,y+1) || canGo(grid,target,loc+1,x,y-1);
        grid[x][y] = temp;
        return signal;
    }
}

}
//时间复杂度(nm*3^length)
//空间复杂度O(length)

0 赞同 0 条回复

王位詮釋普通 2024年3月27日下午9:13

暴力回溯：
主函数：每次找一个左边来进行回溯，如果如果这次回溯直接能出结果那就直接返回，否则进行下一个坐标的回溯。
回溯函数：每次可以选择一个方向做为下一步，如果这一步没超过索引范围并且这个位置没被访问过就走，进入下一次回溯。
class Solution {
    public boolean wordPuzzle(char[][] grid, String target) {
        int h = grid.length;
        int w = grid[0].length;
        boolean[][] visitetd = new boolean[h][w];
        for(int i=0;i<h;i++){
            for(int j = 0;j<w;j++){
                boolean flag = backtrace(grid,i,j,visitetd,target,0);
                if(flag==true){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean backtrace(char[][] grid,int i,int j,boolean[][] visitetd,String target,int count){
        if(target.charAt(count)!=grid[i][j]){//如果长度已经够了就看两者是否相同，否则就返回
            return false;
        }
        if(count==target.length()-1){
            return true;
        }
        visitetd[i][j] = true;
        int[][] directions = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        for(int[] direction:directions){
            int newi = i+direction[0];
            int newj = j+direction[1];
            if(newi<grid.length&&newi>=0&&newj<grid[0].length&&newj>=0){//满足范围
                if(!visitetd[newi][newj]){
                    boolean flag = backtrace(grid,newi,newj,visitetd,target,count+1);
                    if(flag==true){
                        return true;
                    }
                }
            }
        }
        visitetd[i][j] = false;
        return false;
    }
}

0 赞同 0 条回复

Raphtalia. 普通 2024年3月27日下午8:44

class Solution {
public:
bool wordPuzzle(vector<vector>& grid, string target) {
int m = grid.size(), n = grid[0].size();
for(int i = 0; i < m; i ++) {
for(int j = 0; j < n; j ++) {
if(dfs(grid, target, i, j, 0)) return true;
}
}
return false;
}
private:

bool dfs(vector<vector<char>>& grid, string target, int x, int y, int idx) {
    int m = grid.size(), n = grid[0].size();
    if(x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != target[idx]) return false;
    if(idx == target.size() - 1) {
        return true;
    }
    grid[x][y] = ' ';
    bool ans = dfs(grid, target, x + 1, y, idx + 1) || dfs(grid, target, x, y + 1, idx + 1)
    || dfs(grid, target, x - 1, y, idx + 1) ||dfs(grid, target, x, y - 1, idx + 1);
    grid[x][y] = target[idx];
    return ans;
}

};
时间复杂度O(3^KMN) 空间复杂度O（K）

0 赞同 0 条回复

【回溯专题】剑指 Offer 12. 矩阵中的路径

共以下 12 个回答

# 回答此问题取消回复

【回溯专题】剑指 Offer 12. 矩阵中的路径

共以下 12 个回答

# 回答此问题 取消回复

# 回答此问题取消回复