79. Word Search

board为二维数组的情况：

public boolean exist(char[][] board, String word) {
    if (board == null || board.length == 0 || word == null) return false;
    char[] words = word.toCharArray();
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (dfs(board, i, j, words, 0)) return true;
        }
    }
    return false;
}

public boolean dfs(char[][] board, int i, int j, char[] words, int k) {
    if (k == words.length) return true;
    if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != words[k])
        return false;
    // char tmp = board[i][j];
    // board[i][j] = '#';
    board[i][j] ^= 256;
    boolean res = dfs(board, i + 1, j, words, k + 1) ||
        dfs(board, i - 1, j, words, k + 1) ||
        dfs(board, i, j + 1, words, k + 1) ||
        dfs(board, i, j - 1, words, k + 1);
    board[i][j] ^= 256;
    // board[i][j] = tmp;
    return res;
}

matrix为一维数组，直接在matrix数组上进行修改，用临时变量保存或者异或256，做完一次dfs之后将matrix中的字母复原。

public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
    if (matrix == null || matrix.length == 0 || str == null || str.length == 0) 
        return false;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (dfs(matrix, rows, cols, i, j, str, 0)) return true;
        }
    }
    return false;
}

public boolean dfs(char[] matrix, int rows, int cols, int i, int j, char[] str, int k) {
    int index = i * cols + j; // index是字母在一行matrix中的位置
    if (str.length == k) return true;  // in the front
    if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k])
        return false;
    // 1.临时变量
    // char tmp = matrix[index];
    // matrix[index] = '-';
    // 2.异或修改
    matrix[index] ^= 256;
    boolean res = dfs(matrix, rows, cols,i - 1, j, str, k + 1)||
        dfs(matrix,rows, cols, i + 1, j, str, k + 1) ||
        dfs(matrix,rows, cols, i, j - 1, str, k + 1) ||
        dfs(matrix, rows, cols,i, j + 1, str, k + 1);
    matrix[index] ^= 256;
    // matrix[index] = tmp;
    return res;
}

设置flag(visited)数组：

public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
    if (matrix == null || matrix.length == 0 || str == null || str.length == 0) 
        return false;
    boolean[] flag = new boolean[matrix.length];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (dfs(matrix, rows, cols, i, j, str, 0, flag)) return true;
        }
    }
    return false;
}

public boolean dfs(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, boolean[] flag) {
    int index = i * cols + j;
    if (str.length == k) return true;
    if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index]) 
        return false;
    flag[index] = true;
    boolean res = dfs(matrix, rows, cols,i - 1, j, str, k + 1, flag)||
        dfs(matrix,rows, cols, i + 1, j, str, k + 1, flag) ||
        dfs(matrix,rows, cols, i, j - 1, str, k + 1, flag) ||
        dfs(matrix, rows, cols,i, j + 1, str, k + 1, flag);
    flag[index] = false;
    return res;
}

最佳解答，设置额外的visited数组（同上）每次在主函数中进行loop的时候visited数组都是false，并且简化dfs的写法

    private static boolean[][] visited;
    private static final int[][] distance = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static boolean wordSearchWithTable(char[][] board, String s) {
        if (board == null || board.length == 0 || board[0].length == 0) return false;
//        if (s == null || s.length() == 0) return false;

        visited = new boolean[board.length][board[0].length];
        char[] letters = s.toCharArray();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // all elements in visited are false for every loop
                if (dfs2(board, i, j, letters, 0)) return true;
            }
        }
        return false;
    }

    private static boolean dfs2(char[][] board, int i, int j, char[] letters, int pointer) {
        if (pointer == letters.length) return true;
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != letters[pointer] || visited[i][j])
            return false;
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int newX = i + distance[k][0];
            int newY = j + distance[k][1];
            if (dfs2(board, newX, newY, letters, pointer + 1)) return true;
        }
        visited[i][j] = false;
        return false;
    }

机器人的运动范围：

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路：

1. 设置一个visited数组记录访问过的位置。
2. 递归终止条件：超出边界 or 已经访问过 or 超出坐标阈值
3. 标记
4. dfs + 1

public int movingCount(int threshold, int rows, int cols)
{
    boolean[][] visited = new boolean[rows][cols];
    return dfs(threshold, rows, cols, 0, 0, visited);
}

public int dfs(int threshold, int rows, int cols, int i, int j, boolean[][] visited) {
    if (i < 0 || j < 0 || i >=rows || j >= cols || visited[i][j] || getSum(i) + getSum(j) > threshold) 
        return 0;
    visited[i][j] = true;
    return dfs(threshold, rows, cols, i - 1, j, visited) +
        dfs(threshold, rows, cols, i + 1, j, visited) +
        dfs(threshold, rows, cols, i, j - 1, visited) + 
        dfs(threshold, rows, cols, i, j + 1, visited) + 1;
}

// 得到行或者列每位的和
public int getSum(int t){
    int sum = 0;
    while (t != 0){
        sum += t % 10;
        t /= 10;
    }
    return  sum;
}