/*
Runtime: 7 ms
Memory Usage: 38.3 MB
*/
class Solution {
    public boolean exist(char[][] board, String word) {
        if (board.length == 0 || board[0].length == 0) {
            return false;
        }
        if (word == null || word.length() == 0) {
            return false;
        }

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

        for (int r = 0; r < board.length; r++)
            for (int c = 0; c < board[r].length; c++ ) {
                visited[r][c] = false;
            }


        for (int r = 0; r < board.length; r++)
            for (int c = 0; c < board[r].length; c++ ) {
                if (exist(board, word, 0, r, c, visited)) {
                    return true;
                }
            }

        return false;
    }

    public boolean exist(char[][] board, String word, int pos, int r, int c, boolean[][] visited) {
        if (board[r][c] != word.charAt(pos)) {
            return false;
        }

        if (pos == word.length() - 1) {
            return true;
        }

        int[][] next = new int[][] {
            { r, c + 1 },
            { r, c - 1},
            { r + 1, c },
            { r - 1, c }
        };

        visited[r][c] = true;

        for (int i = 0; i < 4; i++) {
            int newR = next[i][0];
            int newC = next[i][1];

            if (newR < 0 || newR >= board.length || newC < 0 || newC >= board[0].length) {
                continue;
            }

            if (visited[newR][newC]) {
                continue;
            }

            if (exist(board, word, pos + 1, newR, newC, visited)) {
                return true;
            }
        }

        visited[r][c] = false;

        return false;
    }
}