[leetcode]Word Search

又是一个DFS。犯过的一个错误是，上下左右移动的时候，不需要x，y一起变，只要变一个就行了。

在参考答案里面，把访问过得格子标为'#'特殊字符，就可以省去visited数组，但这样会改变原来的数组。

http://discuss.leetcode.com/questions/254/word-search

public class Solution {
    public boolean exist(char[][] board, String word) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        int m = board.length;
        if (m == 0) return false;
        int n = board[0].length;
        if (n == 0) return false;
        
        boolean[][] visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, visited, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board, boolean[][] visited, int x, int y, String word, int idx) {
        if (!visited[x][y] && board[x][y] == word.charAt(idx)) {
            visited[x][y] = true;
            if (idx == word.length()-1) return true;
            if (x-1 >= 0 && dfs(board, visited, x-1, y, word, idx+1)) return true;           
            if (x+1 < board.length && dfs(board, visited, x+1, y, word, idx+1)) return true;
            if (y-1 >= 0 && dfs(board, visited, x, y-1, word, idx+1)) return true;
            if (y+1 < board[0].length && dfs(board, visited, x, y+1, word, idx+1)) return true;            
            visited[x][y] = false;
        }
        return false;
    }
}