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;
        }

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

        return false;
    }

    public boolean exist(char[][] board, String word, int pos, int r, int c, int fromR, int fromC) {
        if (pos >= word.length()) {
            return true;
        }

        if (board[r][c] != word.charAt(pos)) {
            return false;
        }

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

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

            if (newR == fromR && newC == fromC) {
                continue;
            }

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

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

        return false;
    }
}