回溯问题

从网格中寻找单词

package com.data.stringDemo;

/**
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母不允许被重复使用。
 *
 * board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 *
 * 给定 word = "ABCCED", 返回 true
 * 给定 word = "SEE", 返回 true
 * 给定 word = "ABCB", 返回 false
 *
 */

/**
 * 思路使用递归回溯的方法
 * 需要定义一个二维boolean类型的数组，用来存储当前位置是否能走通
 *
 */

public class searchWord {
    public static void main(String[] args) {
        char[][] array = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        Solution solution = new Solution();
        boolean result = solution.exist(array, "ABCCED");
        System.out.println(result);
    }
}


class Solution {
    public boolean exist(char[][] board, String word) {
        boolean[][] visited = 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 (word.charAt(0) == board[i][j] && backtrack2(i, j, 0, word, visited, board))
                    return true;
            }
        }
        return false;
    }


    private boolean backtrack2(int i, int j, int idx, String word, boolean[][] visited, char[][] board) {
        if (idx == word.length()) return true;
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word.charAt(idx) || visited[i][j])
            return false;
        visited[i][j] = true;

        //向下找
        if (backtrack2(i + 1, j, idx + 1, word, visited, board)) {
            return true;
        }
        //向上找
        if (backtrack2(i - 1, j, idx + 1, word, visited, board)) {
            return true;
        }
        //向右
        if (backtrack2(i, j + 1, idx + 1, word, visited, board)) {
            return true;
        }
        //向左
        if (backtrack2(i, j - 1, idx + 1, word, visited, board)) {
            return true;
        }

        visited[i][j] = false; // 回溯
        return false;
    }

}