package LeetCode;

public class LeetCode79 {

    // https://leetcode-cn.com/problems/word-search/description/

    /// 回溯法
    /// 时间复杂度: O(m*n*m*n)
    /// 空间复杂度: O(m*n)

    // 左，上，右，下移动
    private int d[][] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private int m, n;
    private boolean[][] visited;

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

        if (board == null || word == null)
            throw new IllegalArgumentException("board or word can not be null!");

        m = board.length;
        if (m == 0)
            throw new IllegalArgumentException("board can not be empty.");
        n = board[0].length;
        if (n == 0)
            throw new IllegalArgumentException("board can not be empty.");

        visited = new boolean[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (searchWord(board, word, 0, i, j))
                    return true;

        return false;
    }

    // 判断坐标是否在区域内
    private boolean inArea(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    // 从board[startx][starty]开始, 寻找word[index...word.size())
    private boolean searchWord(char[][] board, String word, int index,
                               int startx, int starty) {

        //assert(inArea(startx,starty));
        if (index == word.length() - 1)
            return board[startx][starty] == word.charAt(index);

        if (board[startx][starty] == word.charAt(index)) {
            visited[startx][starty] = true;
            // 从startx, starty出发,向四个方向寻
            for (int i = 0; i < 4; i++) {
                int newx = startx + d[i][0];
                int newy = starty + d[i][1];
                if (inArea(newx, newy) && !visited[newx][newy] &&
                        searchWord(board, word, index + 1, newx, newy))
                    return true;
            }
            visited[startx][starty] = false;
        }
        return false;
    }

    public static void main(String args[]) {

        char[][] b1 = {{'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}};

        String words[] = {"ABCCED", "SEE", "ABCB"};
        for (int i = 0; i < words.length; i++)
            if ((new LeetCode79()).exist(b1, words[i]))
                System.out.println("found " + words[i]);
            else
                System.out.println("can not found " + words[i]);

        // ---
        char[][] b2 = {{'A'}};
        if ((new LeetCode79()).exist(b2, "AB"))
            System.out.println("found AB");
        else
            System.out.println("can not found AB");
    }
}