题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思路

1. 用深度优先搜索，从网格中的每个单词开始依次从上下左右四个方向搜索相邻的单词
2. 如果搜索到的字母与字符串中对应位置的字母相等，则继续搜索
3. 如果到达网格边界或者搜索的字母不相等则退出返回fasle，如果最后一个单词搜索完毕则返回true
4. 只要四个方向有一个返回true，则不在搜索返回true

代码

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || word =="") {
            return false;
        }
        char []chars = word.toCharArray();
        boolean[][] mark = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, chars, mark, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] chars, boolean[][] mark, int i, int j, int s){
        if (i < 0||i >= board.length||j < 0||j >= board[0].length||chars[s]!=board[i][j]||mark[i][j])
            return false;
        if (s == chars.length - 1)
            return true;

        mark[i][j] = true;
        s++;
        boolean res = dfs(board, chars, mark, i + 1, j, s)
            || dfs(board, chars, mark, i - 1, j, s)
            || dfs(board, chars, mark, i, j + 1, s)
            || dfs(board, chars, mark, i, j - 1, s);
        mark[i][j] = false;
        return res;
    }


    public static void main(String[] args) {
        char[][]board = {{‘A‘,‘B‘,‘C‘,‘E‘},
                        {‘S‘,‘F‘,‘C‘,‘S‘},
                        {‘A‘,‘D‘,‘E‘,‘E‘}};
        String word = "ABCCED";
        System.out.println(new Solution().exist(board, word));
    }
}

矩阵中的路径

原文：https://www.cnblogs.com/chengejie/p/14856652.html