package cn.iocoder.yudao.framework.common.thealgorithms.backtracking;

///*
//Word Search Problem (https://en.wikipedia.org/wiki/Word_search)
//
//Given an m x n grid of characters board and a string word, return true if word exists in the grid.
//
//The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are
//those horizontally or vertically neighboring. The same letter cell may not be used more than once.
//
//For example,
//Given board =
//
//[
// ['A','B','C','E'],
// ['S','F','C','S'],
// ['A','D','E','E']
//]
//word = "ABCCED", -> returns true,
//word = "SEE", -> returns true,
//word = "ABCB", -> returns false.
//*/
//
///*
//   Solution
//   Depth First Search in matrix (as multiple sources possible) with backtracking
//   like finding cycle in a directed graph. Maintain a record of path
//
//   Tx = O(m * n * 3^L): for each cell, we look at 3 options (not 4 as that one will be visited), we
//   do it L times Sx = O(L) : stack size is max L
//*/
//
//public class WordSearch {
//    private final int[] dx = {0, 0, 1, -1};
//    private final int[] dy = {1, -1, 0, 0};
//    private boolean[][] visited;
//    private char[][] board;
//    private String word;
//
//    private boolean isValid(int x, int y) {
//        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
//    }
//
//    private boolean doDFS(int x, int y, int nextIdx) {
//        visited[x][y] = true;
//        if (nextIdx == word.length()) {
//            return true;
//        }
//        for (int i = 0; i < 4; ++i) {
//            int xi = x + dx[i];
//            int yi = y + dy[i];
//            if (isValid(xi, yi) && board[xi][yi] == word.charAt(nextIdx) && !visited[xi][yi]) {
//                boolean exists = doDFS(xi, yi, nextIdx + 1);
//                if (exists) {
//                    return true;
//                }
//            }
//        }
//        visited[x][y] = false;
//        return false;
//    }
//
//    public boolean exist(char[][] board, String word) {
//        this.board = board;
//        this.word = word;
//        for (int i = 0; i < board.length; ++i) {
//            for (int j = 0; j < board[0].length; ++j) {
//                if (board[i][j] == word.charAt(0)) {
//                    visited = new boolean[board.length][board[0].length];
//                    boolean exists = doDFS(i, j, 1);
//                    if (exists) {
//                        return true;
//                    }
//                }
//            }
//        }
//        return false;
//    }
//}



/*
单词搜索问题 (https://en.wikipedia.org/wiki/Word_search)

给定一个 m x n 的字符网格 board 和一个字符串 word，如果 word 在网格中存在，则返回 true。

单词可以由顺序相邻单元格的字母构成，其中“相邻”单元格是水平或垂直相邻的单元格。
同一个字母单元格不得使用超过一次。

例如，
给定 board =

[
 ['A','B','C','E'],
 ['S','F','C','S'],
 ['A','D','E','E']
]
word = "ABCCED", -> 返回 true,
word = "SEE", -> 返回 true,
word = "ABCB", -> 返回 false.
*/

/*
   解决方案
   在矩阵中进行深度优先搜索（因为可能有多个源）并回溯
   类似于在有向图中寻找循环。保持路径记录

   时间复杂度 Tx = O(m * n * 3^L): 对于每个单元格，我们查看 3 个选项（不是 4 个，因为那个已经被访问过了），我们
   做 L 次 空间复杂度 Sx = O(L) : 栈的大小最大为 L
*/

public class WordSearch {
    private final int[] dx = {0, 0, 1, -1}; // x 方向的移动
    private final int[] dy = {1, -1, 0, 0}; // y 方向的移动
    private boolean[][] visited; // 访问标记数组
    private char[][] board; // 字符网格
    private String word; // 要搜索的单词

    // 检查坐标 (x, y) 是否有效
    private boolean isValid(int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }

    // 执行深度优先搜索
    private boolean doDFS(int x, int y, int nextIdx) {
        visited[x][y] = true;
        if (nextIdx == word.length()) {
            return true;
        }
        for (int i = 0; i < 4; ++i) {
            int xi = x + dx[i];
            int yi = y + dy[i];
            if (isValid(xi, yi) && board[xi][yi] == word.charAt(nextIdx) && !visited[xi][yi]) {
                boolean exists = doDFS(xi, yi, nextIdx + 1);
                if (exists) {
                    return true;
                }
            }
        }
        visited[x][y] = false; // 回溯
        return false;
    }

    // 判断单词是否存在于网格中
    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                if (board[i][j] == word.charAt(0)) {
                    visited = new boolean[board.length][board[0].length];
                    boolean exists = doDFS(i, j, 1);
                    if (exists) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
