矩阵中的路径

medium 原题连接：矩阵中的路径

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

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

示例：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

限制：

  1. m == board.length

  2. n = board[i].length

  3. 1 <= m, n <= 6

  4. 1 <= word.length <= 15

  5. board 和 word 仅由大小写英文字母组成

解题思路

本题其实主要需要解决两个问题：单词会从何开始，单词要怎么结束

前者可以使用暴力递归，遍历二维数组，找到符合字符串首字符的即可

后者需要以前者找到的字符串为基础，探索上下左右是否有相邻字符，直至单词结尾

需要注意的是，上下左右的探索需要排除明显超出二位数组范围的部分，和已经探索完成的部分

我使用一个临时变量，存储已经遍历的值，这使得如果单词匹配中出现了误差，需要另找开头字符，不至于将上次遍历的痕迹影响到此次

Java代码

class Solution {
    public boolean exist(char[][] board, String word) {
        // 1.如何开始找单词 -- 第一个字符组字怎么找
        // 2.如果在遍历中传递对比值 -- 考虑算法需要回溯
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[0].length; j++) {
                if(dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean dfs(char[][] board, int i, int j, String word, int k) {
        int sizeA = board.length,sizeB = board[0].length;
        if(i == sizeA || i == -1 || j == sizeB || j == -1 || board[i][j] != word.charAt(k)) return false;
        if(k == word.length()-1) return true;
        char mid = board[i][j];
        // 挖空以遍历部分，防止重复读
        board[i][j] = ' ';
        boolean ans = dfs(board,i+1,j,word,k+1) || dfs(board,i-1,j,word,k+1)
                   || dfs(board,i,j+1,word,k+1) || dfs(board,i,j-1,word,k+1);
        // 回复挖空，保证下次读
        board[i][j] = mid;
        return ans;
    }
}

机器人的运动范围

medium 原题连接：机器人的运动范围

地上有一个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。请问该机器人能够到达多少个格子？

示例：

输入：m = 2, n = 3, k = 1
输出：3
输入：m = 3, n = 1, k = 0
输出：1

提示：

  1. 1 <= n,m <= 100
  2. 0 <= k <= 20

解题思路

本题不可以暴力遍历，考虑到机器人对目标是需要移动手段的，有些符合要求但是机器人却没法到达的部分是不能算作结果的一部分

那么较好的方法是模拟机器人，从[0,0]向左向下递归遍历，走遍相邻的符合条件的格子并计数

但是没有对应的二维数组存储已走过的路程信息，只能新new一个用于判断的二维boolean数组，避免重复计数

Java代码

class Solution {
    public int m,n,k;
    public int movingCount(int m, int n, int k) {
       this.m = m; this.n = n; this.k = k;
       boolean[][] flag = new boolean[m][n];
       return dfs(flag,0,0);
    }

    public int dfs(boolean[][] flag, int i, int j) {
        if(i >= m || j>=n || flag[i][j] || getSum(i,j)>k) return 0;
        flag[i][j] = true;
        return 1 + dfs(flag, i+1, j) + dfs(flag, i,j+1);
    }

    public int getSum(int i, int j) {
        int sum = 0;
        while(i > 0) {
            sum += i%10;
            i = i/10;
        }
        while(j > 0) {
            sum += j%10;
            j = j/10;
        }
        return sum;
    }
}