题解 | #机器人的运动范围#

import java.util.*;
public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        int [][] matrix = new int[rows][cols];
        int[][] visit = new int[rows][cols];
        int[][] visitAll = new int[rows][cols];
        // for (int i = 0; i < rows; i++)
        //     for (int j = 0; j < cols; j++) {
        //         matrix[i][j] = sumWei(i) + sumWei(j);
        //     }
        int []xy = {0, 0};
        visitAll[0][0] = 1;
        dfs(threshold, matrix, 0, 0, visit, visitAll);
        int sum = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (visitAll[i][j] == 1) {
                    sum++;
                }
            }
        }
        return sum;
    }
    public void dfs(int threshold,
                     int matrix[][], int x, int y, int[][] visit, int[][] visitAll) {
                for (int i = -1; i < 2; i++)
                    for (int j = -1; j < 2; j++) {
                        if (i != j &&
                                i != -1 * j) {//满足条件的i,j组合为{-1,0},{0,-1},{1,0},{0,1}，即上下左右四个方向
                            int posX = x+ i;
                            int posY = y + j;
                            if (posX < matrix.length && posX >= 0 && posY < matrix[0].length && posY >= 0) {
                                if (sumWei(posX) + sumWei(posY) <= threshold && visit[posX][posY] == 0 ) {
                                    visit[posX][posY] = 1;//只要访问过的就不再访问                                 
                                    visitAll[posX][posY] = 1;//标记能到达的点
                                    dfs(threshold, matrix, posX, posY, visit, visitAll);
                                }
                            }

                        }
                    }
        }
    public int sumWei(int num) {
        int sum = 0;
        int numy = num % 10;
        int numz = num / 10;
        sum = sum + numy;
        while (numz > 0) {
            numy = numz % 10;
            numz = numz / 10;
            sum = sum + numy;
        }
        return sum;
    }
}