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

June 普通 2023年9月16日下午7:10

class Solution {
    boolean hasWord = false;
    boolean[][] vis;
    int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int n,m;

    public void init()
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                vis[i][j] = false;
    }

    public boolean exist(char[][] board, String word) {
        n = board.length;
        if (n == 0)
            return false;
        m = board[0].length;
        vis = new boolean[n][m];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(board[i][j] == word.charAt(0)) {
                     init();
                     dfs(i,j,board,word,"");
                }
                if(hasWord)
                    return true;
            }
        }
        return hasWord;
    }

    public void dfs(int x,int y,char[][] board,String word,String path)
    {
        String newPath = path + board[x][y];
       // System.out.println(newPath);
        if(newPath.equals(word))
        {
            hasWord = true;
            return;
        }
        if(newPath.length() > word.length() || word.indexOf(newPath) != 0)
            return; // 剪枝
        vis[x][y] = true;

        for(int k=0;k<4;k++)
        {
            int ux = x + dir[k][0];
            int uy = y + dir[k][1];
            if(ux >= n || ux < 0 || uy >= m || uy < 0)
                continue;
            if(vis[ux][uy])
                continue;
            dfs(ux, uy, board, word ,newPath);
            vis[ux][uy] = false;
        }
    }
}

0 赞同 0 条回复

ppopp 普通 2023年9月9日下午4:17

class Solution {
public:
bool exist(vector<vector>& board, string word) {
//遍历每一个结点
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board[i].size(); j++){
if(dfs(board, word, 0, i, j)) return true;
}
}
return false;
}

//设定方向数组
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

//起点，依次遍历四周，枚举下一个字母对应
//直到遍历到最后一个字母能对应上，然后返回true
bool dfs(vector<vector<char>>& board, string& word, int cur, int x, int y){
    //从当前位置开始搜索,如果不是，退
    if(board[x][y] != word[cur]) return false;
    //如果目前进行到最后一个且相等，返回true
    if(cur == word.size() - 1) return true;
    //另存当前数值，将原位置数值另置，同一个单元格位置不可重复使用
    char t = board[x][y];
    board[x][y] = '*';
    for(int i = 0; i < 4; i++){
        //移动
        int a = x + dx[i], b = y + dy[i];
        //超出范围或者已经搜索过，继续，
        if(a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '*')
            continue;
        if(dfs(board, word, cur+1, a, b)){
            return true;
        }
    }
    //退出来
    board[x][y] = t;
    return false;
}

};

0 赞同 0 条回复

Marshan 普通 2023年8月22日下午11:30

第二次做了还是没有独立写出来，回溯掌握的依旧不好还要加强。

class Solution {
public:
    // bool result = false;
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size();
        int m = board[0].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((word[0] == board[i][j]) && func(board,visited,word,0,i,j)){
                    return true;
                }
            }
        }
        return false;
    }
    bool func(vector<vector<char>>& board, vector<vector<bool>>& visited, string word, int index, int x, int y){
        if((x < 0) || (x >= board.size()) || (y < 0) || (y >= board[0].size()) || (visited[x][y]) || (word[index] != board[x][y])){
            return false;
        }
        if(index == word.size() - 1){
            return true;
        }

        index++;
        visited[x][y] = true;

        bool res = func(board,visited,word,index,x,y+1) ||
                    func(board,visited,word,index,x+1,y) ||
                    func(board,visited,word,index,x,y-1) ||
                    func(board,visited,word,index,x-1,y);

        index--;
        visited[x][y] = false;

        return res;
    }
};

0 赞同 0 条回复

普通 2023年8月22日下午11:21

c++ 代码
class Solution {
public:
int cx[4]={-1,1,0,0},cy[4]={0,0,-1,1},k=0;
bool exist(vector<vector>& board, string word)
{
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[0].size();j++)
{
if(dfs(board,i,j,word,k))
return true;
}
}
return false;

}
bool dfs(vector<vector<char>>& board,int n,int m,string world,int k)
{
    if(n<0||n>=board.size()||m<0||m>=board[0].size()||board[n][m]!=world[k]) return false;
    if(k==world.size()-1) return true;
    board[n][m]='*';

     bool re=dfs(board,n+1,m,world,k+1)||dfs(board,n-1,m,world,k+1)||dfs(board,n,m+1,world,k+1)||dfs(board,n,m-1,world,k+1);
     board[n][m]=world[k];
  return re;
}

};

0 赞同 0 条回复

人生何处不青山普通 2023年8月20日下午11:19

回溯

function exist(board: string[][], word: string): boolean {
    let m = board.length, n = board[0].length;
    const dx = [1, 0, -1, 0], dy = [0, -1, 0, 1];
    const dfs = (i: number, j: number, k: number) => {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word.charAt(k) || board[i][j] === '#') return false;
        if (k === word.length - 1) return true;
        board[i][j] = '#';
        for (let t = 0; t < 4; t++) {
            let a = i + dx[t], b = j + dy[t];
            if (dfs(a, b, k + 1)) return true;
        }
        board[i][j] = word.charAt(k);
        return false;
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(i, j, 0)) return true;
        }
    }
    return false;
};

0 赞同 0 条回复

Mby 普通 2023年8月14日下午12:28

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(dfs(board, i , j, word, 0)){
                    return true;
                }
            }
        }
            return false;
    }
    boolean dfs(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';
        //四个方向都搜索一下
        boolean res = dfs(board, i, j + 1, word, k + 1) ||
                    dfs(board, i + 1, j, word, k + 1) ||
                    dfs(board, i, j - 1, word, k + 1) ||
                    dfs(board, i - 1, j, word, k + 1);

        board[i][j] = word.charAt(k);
        return res;
        //时间复杂度： mn * 3^len
    }
}

0 赞同 0 条回复

CKX 普通 2023年8月10日下午5:22

func exist(board [][]byte, word string) bool {
    n := len(board)
    m := len(board[0])
    l := len(word)
    visited := make([][]bool, n)
    for i := range visited {
        visited[i] = make([]bool, m)
    }
    var backtrack func(int,int,int) bool
    backtrack = func(i, j, k int) bool {
        if i < 0 || i >= n || j < 0 || j >= m || visited[i][j] || board[i][j] != word[k] {
            return false
        }
        if k == l-1 {
            //长度符合
            return true
        }
        visited[i][j] = true
        res := backtrack(i, j+1, k+1) || backtrack(i+1,j,k+1) || backtrack(i, j-1, k+1) || backtrack(i-1, j, k+1)
        visited[i][j] = false
        return res
    }

    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if backtrack(i, j, 0) {
                return true
            }
        }
    }
    return false
}

0 赞同 0 条回复

北辰普通 2023年8月9日下午8:04

java
class Solution {

    public int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};

    public boolean exist(char[][] board, String word) {
        int h = board.length,w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for(int i=0;i<h;i++) {
            for(int j=0;j<w;j++) {
                boolean flag = check(board,visited,i,j,word,0);
//对每个元素都进行判断
                if(flag) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if(board[i][j]!=s.charAt(k)) {
            return false;
        }else if(k == s.length()-1) {
            return true;
        }
        visited[i][j]=true;
        boolean result = false;
        for(int m=0;m<4;m++) {
            int newi = i+dir[m][0],newj = j+dir[m][1];
            if(newi>=0&&newi<board.length&&newj>=0&&newj<board[0].length&&visited[newi][newj]==false) {
                boolean flag = check(board,visited,newi,newj,s,k+1);
                if(flag) {
                    result = true;
                    break;
                }
            }
        }
        visited[i][j]=false;
        return result;
    }
}

0 赞同 0 条回复

#00456B 普通 2023年8月8日下午11:58

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size();
        if(n == 0){
            return false;
        }
        int m = board[0].size();
        int len = word.size();
        vector<vector<bool>> visited(n,vector<bool>(m, false));//记录这个节点是否访问过

        function<bool(int, int, int)> dfs = [&](int i, int j, int k) -> bool{//ij是在二维数组中的访问下标，k是word里面的下标
            //ij越界、当前位置已经访问过、当前位置不满足word的条件，都返回false
            if(i < 0 || i>= n || j < 0 || j >= m || visited[i][j] || board[i][j] != word[k]){
                return false;
            }
            //如果word遍历完了
            if(k == len - 1){
                return true;
            }
            //对这个节点开始右下左上，四个方位进行探索
            visited[i][j] = true;//先表示来过这个位置
            bool ans = 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改回0
            visited[i][j] = false;
            return ans;
        };

        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 条回复

CaCO3 永久会员 2023年8月5日上午10:38

”’java
class Solution {
public boolean exist(char[][] board, String word) {
//回溯算法，相邻单词连接起来
int h = board.length,w=board[0].length;
boolean[][] visited = new boolean[h][w];
for(int i = 0;i < h;i++){
for(int j = 0;j < w;j++){
boolean flag = check(board,visited,i,j,word,0);
if(flag){
return true;
}
}
}
return false;
}

public boolean check(char[][] board,boolean[][] visited,int i,int j,String s,int k){
    if(board[i][j] != s.charAt(k)){
        return false;
    }else if(k == s.length() - 1){
        return true;
    }
    visited[i][j] = true;
    int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
    boolean result = false;
    for(int[] dir:directions){
        int newi = i+dir[0],newj=j+dir[1];
        if(newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length){
            if(!visited[newi][newj]){//判断是否浏览过
                boolean flag = check(board,visited,newi,newj,s,k+1);
                if(flag){
                    result = true;
                    break;
                }
            }
        }
    }
    visited[i][j] = false;//标记是否访问过
    return result;
}

}
”’

0 赞同 0 条回复

NullPointerException 普通 2023年8月4日下午7:50

class Solution {
int n;
int m;
boolean[][] jude;
public boolean exist(char[][] board, String word) {
//回溯用数组标记已经走过加入结果集
//从每一个点开始
n=board.length;
m=board[0].length;
jude=new boolean[n][m];
for(int i=0;i<board.length;i++)
{
for(int j =0;j<board[0].length;j++)
{
if(backing(board,word,i,j,0))//定义k 判断word的第几位和 board(i,j)比较相同才能走循环
{
return true;
}
}
}
return false;

}
public boolean backing(char[][] board,String word,int i,int j,int k)
{

if(i<0||i>=n||j<0||j>=m||board[i][j]!=word.charAt(k)||jude[i][j])
{
return false;
}
if(kword.length()-1)
{
return true;
}
jude[i][j]=true; //默认false
boolean res = backing(board,word,i+1,j,k+1)||backing(board,word,i,j+1,k+1)||backing(board,word,i-1,j,k+1)||backing(board,word,i,j-1,k+1);

jude[i][j]=false;
return res;


}

}

0 赞同 0 条回复

AD钙奶普通 2023年8月4日下午12:56

做的比较少，思考了挺久

class Solution {
    public boolean exist(char[][] board, String word) {
        boolean[][] used = new boolean[board.length][board[0].length];
        char[] chars = word.toCharArray();
        for(int i = 0; i < board.length; i ++) {
            for(int j = 0; j < board[0].length; j ++) {               
                if(backTracking(board,i,j,used,0,chars)){
                    return true;
                }                
            }
        }
        return false;
    }

    public boolean backTracking(char[][] board, int row, int column, boolean[][] used, int index, char[] chars) {
        if(index == chars.length) return true;
        if(row < 0 || column < 0 || row >= board.length || column >= board[0].length) {
            return false;
        }
        if(used[row][column] || board[row][column] != chars[index]) {
            return false;
        }

        used[row][column] = true;
        boolean res = backTracking(board,row + 1,column,used,index + 1,chars) ||
                    backTracking(board,row,column + 1,used,index + 1,chars) ||
                    backTracking(board,row,column - 1,used,index + 1,chars) ||
                    backTracking(board,row - 1,column,used,index + 1,chars);
        used[row][column] = false;

        return res;
    }
}

0 赞同 0 条回复

阿尚普通 2023年8月2日下午11:39

class Solution {
    int[][] record;//记录一次dfs已经遍历过的位置
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        record = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(dfs(board, i, j, word, 0)){
                    return true;
                }
            }
        }
        return false;

    }

    public boolean dfs(char[][] board, int i, int j, String word, int index){
        if(index == word.length()){
            return true;
        }

        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length){
            return false;
        }
        if(record[i][j] == 1){
            return false;
        }
        if(board[i][j] != word.charAt(index)){
            return false;
        }

        record[i][j] = 1;

        boolean up = dfs(board, i - 1, j, word, index + 1);
        boolean down = dfs(board, i + 1, j, word, index + 1);
        boolean left = dfs(board, i, j - 1, word, index + 1);
        boolean right = dfs(board, i, j + 1, word, index + 1);

        record[i][j] = 0;

        return up || down || left || right;
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月2日下午11:14

8.2
Day24：下面是代码

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, char[] word, int i, int j, int k){
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word[k]){
            return false;
        }
        if(k == word.length - 1) return true;
        // 访问过的标记空字符串，“ ”是空格 '\0'是空字符串
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    } 
}

0 赞同 0 条回复

mpweixin用户普通 2023年8月2日下午3:51

 //回溯法 + 深度优先遍历DFS + 递归
class Solution {
        public boolean exist(char[][] board, String word) {
            int h = board.length, w = board[0].length;
            boolean[][] visited = new boolean[h][w];
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    // 这个i,j标注的是起点位置
                    boolean flag = check(board, visited, i, j, word, 0);
                    if (flag) {
                        return true;
                    }
                }
            }
            return false;
        }


        public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
            int n = board.length;
            int m = board[0].length;
            if (i<0 || i>=n || j<0 || j>=m || visited[i][j] || board[i][j] != s.charAt(k)) {
                return false;
            }
            if (k == s.length() - 1) {
                return true;
            }
            visited[i][j] = true;
            boolean result = check(board, visited, i, j+1, s, k+1) ||
                             check(board, visited, i+1, j, s, k+1) ||
                             check(board, visited, i, j-1, s, k+1) ||
                             check(board, visited, i-1, j, s, k+1);
            visited[i][j] = false;
            return result;
        }




    }

0 赞同 0 条回复

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

共以下 15 个回答

# 回答此问题取消回复

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

共以下 15 个回答

# 回答此问题 取消回复

# 回答此问题取消回复