12题目描述：

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

解析：

深度优先遍历和剪枝
1.首先把字符串换成数组，然后for循环遍历,递归参数是当前元素在矩阵board中的行列索引i和j，当前目标字符在word中的索引k
2.如果找到该字符，则返回true，否则返回false
3.dfs的递归工作
（1）标记当前矩阵元素：将board[i][j]修改为字符‘#’，代表元素已访问过，防止之后搜索时重复访问；
（2）搜索下一单元格：朝当前元素的上下左右四个方向开启下层递归，使用或连接（代表只需找到一条可行路径及直接返回，不再做后续DFS）,并记录结果至res；
（3）还原当前矩阵元素：将board[i][j]元素还原至初始值，即word[k]；
（4）返回布尔量res，代表是否搜索到目标字符。

Java:

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

JavaScript:

var exist = function(board, word) {
    for(let i = 0; i < board.length; i++) {
        for(let j = 0; j < board[0].length; j++) {
            if(dfs(i, j, 0)) {
                return true;
            }
        }
    }
    return false;

    function dfs(i, j, k) {
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || word[k] !== board[i][j]) {
            return false;
        }
        if(k === word.length - 1) {
            return true;
        }
        let tmp = board[i][j];
        board[i][j] = '#';
        let res =
        dfs(i - 1, j, k + 1) ||
        dfs(i + 1, j, k + 1) ||
        dfs(i, j - 1, k + 1) ||
        dfs(i, j + 1, k + 1);
        board[i][j] = tmp;
        return res;
    }
};

13题目描述：

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

解析：

深度优先遍历算法和剪枝
1.递归参数：当前元素在矩阵中的行列索引i、j，边界m、n，目标值k和visit数组。
2.终止条件： 当行列索引越界或数位和超出目标值k或当前元素已访问过时，返回0，代表不计入可达解。
递推工作：
3.标记当前单元格：将索引 (i, j) 存入visit中，代表此单元格已被访问过。
搜索下一单元格：计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。
4.回溯返回值：返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。

Java：

public int movingCount(int m, int n, int k) {
        boolean[][] visit = new boolean[m][n];
        return dfs(0, 0, m, n, k, visit);
    }
    private int dfs(int i, int j, int m, int n, int k,boolean visit[][]) {
        if(i < 0 || i >= m || j < 0 || j >= n || (i/10 + i%10 + j/10 + j%10) > k || visit[i][j]) {
            return 0;
        }
        visit[i][j] = true;
        return
        dfs(i - 1, j, m, n, k, visit) +
        dfs(i + 1, j, m, n, k, visit) +
        dfs(i, j - 1, m, n, k, visit) +
        dfs(i, j + 1, m, n, k, visit) + 1;
    }

JavaScript:

var movingCount = function(m, n, k) {
    var visit = new Array(m).fill(0).map(() => new Array(n).fill(false));
    var res = 0;
    var dfs = function(i, j) {
        if(i < 0 || i >= m || j < 0 || j >= n || visit[i][j]) {
            return;
        }
        visit[i][j] = true;
        if(canEnter(i, j, k)) {
            res++;
            dfs(i + 1, j);
            dfs(i - 1, j);
            dfs(i,j + 1);
            dfs(i, j - 1);
        }
    }
    dfs(0, 0);
    return res; 
};
var canEnter = function(m, n, k) {
    var res = 0;
    while(m) {
        res += m % 10;
        m = Math.floor(m / 10);
    }
    while(n) {
        res += n % 10;
        n = Math.floor(n / 10);
    }
    return res <= k;
}