79. 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 cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

回溯，遍历所有初始元素。
当寻找的字符与当前matrix里的字符相同时，将当前位置记录在visited里，并向下递归搜索四个方向，回溯visited。
当越界或者字符已经visited时返回false。
当寻找到单词的最后一位时，如果当前matrix里的字符与搜索的字符相等，则返回true。反之返回false。

class Solution {
    char[][] bd;
    String wd;
    int[][] visited;
    public boolean exist(char[][] board, String word) {
        boolean ans = false;
        visited = new int[board.length][board[0].length];
        bd = board;
        wd = word;
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                ans = ans || backtracking(i, j, 0);
            }
        }
        return ans;
    }
    
    private boolean backtracking(int i, int j, int n){
        
        if(i < 0 || j < 0 || i >= bd.length || j >= bd[0].length || n >= wd.length()) return false;
        if(visited[i][j] == 1) return false;
        if(n == wd.length()-1) return bd[i][j] == wd.charAt(n); 
        if( bd[i][j] == wd.charAt(n) ){
            n++;
            visited[i][j] = 1;
            boolean a = backtracking(i+1, j, n);
            boolean b = backtracking(i-1, j, n);
            boolean c = backtracking(i, j+1, n);
            boolean d = backtracking(i, j-1, n);
            visited[i][j] = 0;
            return a || b || c || d;
        }
        return false;
    }
}