「剑指Offer」Day14：搜索与回溯算法（中等）

class Solution {
    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 >= board.length || i < 0 || j >= board[0].length || j < 0){
            return false;
        }
        //判断当前矩阵元素与目标字符是否相同
        if(board[i][j] != words[k]){
            return false;
        }
        //若遍历到单词的最后一个元素，就说明包含，返回true
        if(k == words.length - 1){
            return true;
        }
        //将遍历过的元素置为空字符，与目标字符判断返回false
        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;
    }
}

剑指 Offer 13. 机器人的运动范围

题目描述

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

思路

实现代码

class Solution {
    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        Queue<int[]> queue = new LinkedList<int[]>();
        //可将搜索方向缩减为向右和向下
        int[] dx = {0, 1};
        int[] dy = {1, 0};
        boolean[][] vis = new boolean[m][n]; //标记遍历过的位置
        queue.offer(new int[]{0, 0}); //用数组记录x,y坐标
        vis[0][0] = true;
        int ans = 1;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 2; ++i) { //取出当前坐标，分别向右和向下移动，判断是否可达
                int tx = dx[i] + x;
                int ty = dy[i] + y;
                if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) {
                    continue;
                }
                queue.offer(new int[]{tx, ty}); //可达的坐标继续入队
                vis[tx][ty] = true; //遍历过的位置标记为true
                ans++; //累加到达的格子数
            }
        }
        return ans;
    }
    private int get(int x) { //计算数位之和
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
}