剑指offer：机器人的运动范围

心已赠人 2021-06-24 16:10 343阅读 0赞

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

public class Solution {
        int out = 0;
        public int movingCount(int threshold, int rows, int cols)
        {
            int[][] flag = new int[rows][cols];
            find(0,0,rows,cols,threshold,flag);
            return out;
        }
        public void find(int r, int c, int rows, int cols, int thre, int[][] flag){
            if(r<0 || r>=rows || c<0 || c>= cols || flag[r][c]==1 || sum(r)+sum(c)>thre ){
                return;
            }
            flag[r][c] = 1;
            out += 1;
            find(r-1,c,rows,cols,thre,flag);
            find(r+1,c,rows,cols,thre,flag);
            find(r,c-1,rows,cols,thre,flag);
            find(r,c+1,rows,cols,thre,flag);
        }
        public int sum(int num){
            int total=0;
            while(num!=0){
                total += num%10;
                num /= 10;
            }
            return total;
        }
    }

public class Solution {
        public int movingCount(int threshold, int rows, int cols)
        {
            int[][] flag = new int[rows][cols];
            return find(0,0,rows,cols,threshold,flag);
        }
        public int find(int r, int c, int rows, int cols, int thre, int[][] flag){
            if(r<0 || r>=rows || c<0 || c>= cols || flag[r][c]==1 || sum(r)+sum(c)>thre ){
                return 0;
            }
            flag[r][c] = 1;
            return find(r-1,c,rows,cols,thre,flag)
                +find(r+1,c,rows,cols,thre,flag)
                +find(r,c-1,rows,cols,thre,flag)
                +find(r,c+1,rows,cols,thre,flag)
                +1;
        }
        public int sum(int num){
            int total=0;
            while(num!=0){
                total += num%10;
                num /= 10;
            }
            return total;
        }
    }

宽度优先：  
别人的非递归版

public int movingCount(int threshold, int rows, int cols)
        {
           if(rows <= 0 || cols <= 0 || threshold < 0) return 0;
            Stack<Integer> s = new Stack<>();
            boolean[] visited = new boolean[rows * cols];
            int[][] xoy = {
       {0,1,0,-1},{1,0,-1,0}};
            int count = 0;
            s.add(0);
            visited[0] = true;
            while(!s.empty()) {
                int  cur = s.pop();
                count++;
                for (int i = 0; i < 4; i++) {
                    int x = cur % cols + xoy[0][i];
                    int y = cur / cols + xoy[1][i];
                    int sum = getDigitSum(x) + getDigitSum(y);
                    if(x >= 0 && x < cols && y >= 0 && y < rows 
                            && sum <= threshold && !visited[x + y * cols]) {
                        s.add(x + y * cols);
                        visited[x + y * cols] = true;
                    }
                }
            }
            return count;
        }
     
        private int getDigitSum(int i) {//获取位的和
            int sum = 0;
            while(i > 0) {
                sum += i % 10;
                i /= 10;
            }
            return sum;
        }