剑指 Offer 12. 矩阵中的路径

题目链接

题目类似于迷宫的搜索。
需要注意的是，需要首先判断起始搜索的位置，可能有多个起点，都需要一一尝试。
每轮迭代的时候记得将是否遍历标记数组还原为未遍历的状态。

package com.walegarrett.offer;

/**

 * @Author WaleGarrett

 * @Date 2020/12/9 9:09

 */

import java.util.Arrays;

/**

 * [["a","b","c","e"],

 * ["s","f","c","s"],

 * ["a","d","e","e"]]

 * 矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

 * 1 <= board.length <= 200

 * 1 <= board[i].length <= 200

 */

public class Offer_12 {

    private String word;

    private boolean[][] travel;

    private final int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public boolean exist(char[][] board, String word) {

        if(board == null)

            return false;

        if(word.length() == 0)

            return true;

        this.word = word;

        travel = new boolean[board.length][board[0].length];

        for(int i =0; i< board.length; i++){

            for(int j =0; j< board[0].length; j++){

                travel[i][j] = false;

            }

        }

        for(int i =0; i< board.length; i++){

            int len = board[0].length;

            for(int j =0; j< len; j++){

                if(board[i][j] != word.charAt(0))

                    continue;

                travel[i][j] = true;

                if(findPath(board, 0, i, j)){

                    return true;

                }

                travel[i][j] = false;

            }

        }

        return false;

    }

    public boolean findPath(char[][] board, int pos, int x, int y){

        if(pos >= word.length() - 1){

            if(board[x][y] == word.charAt(pos))

                return true;

            return false;

        }

        //遍历四个方向

        for(int i = 0; i< 4; i++){

            int dx = x + direction[i][0];

            int dy = y+ direction[i][1];

            if(dx>=0 && dy>=0 && dx<board.length && dy< board[0].length && !travel[dx][dy]){

                if(board[dx][dy] == word.charAt(pos + 1)){

                    travel[dx][dy] = true;

                    if(findPath(board, pos+1, dx, dy)){

                        travel[dx][dy] = false;

                        return true;

                    }else travel[dx][dy] = false;

                }

            }

        }

        return false;

    }

}

巴特西

剑指 Offer 12. 矩阵中的路径 + 递归 + 深搜 + 字符串问题

剑指 Offer 12. 矩阵中的路径

题目链接

最新文章

热门文章