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

import java.util.*;
public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        int [][] matrix = new int[rows][cols];
        int xlength = matrix.length;
        int ylength = matrix[0].length;
        int[][] visit = new int[rows][cols];
        int[][] visitAll = new int[rows][cols];
        Stack<int[]> stack = new
        Stack ();//stack存路径,类似BFS广搜路径close表，但stack只存当前条路径，弹出后再存别条的路径，BFS的close表存所有经过的路径
        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;
        stack.push(xy);
        dfs(xy, stack, threshold, matrix, rows, cols, visit, visitAll);
        stack.pop();
        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[] xy, Stack<int[]> stack,  int threshold,
                     int matrix[][], int xlength, int ylength, int[][] visit, int[][] visitAll) {

        if (!stack.isEmpty()) {
            if (stack.size() > 0) {
                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 = stack.peek()[0] + i;
                            int posY = stack.peek()[1] + j;
                            if (posX < xlength && posX >= 0 && posY < ylength && posY >= 0) {
                                if (matrix[posX][posY] <= threshold && visit[posX][posY] == 0 ) {
                                    visit[posX][posY] = 1;//只要访问过的就不再访问                                 
                                    visitAll[posX][posY] = 1;//标记能到达的点
                                    int[] xyadd = {posX, posY};
                                    stack.push(xyadd);
                                    //递归之前的为本条递归的内容，直到尽头
                                    dfs(xy, stack, threshold, matrix, xlength, ylength, visit, visitAll);
                                    //递归之后（也是递归到达尽头后）的为下条递归设置的条件
                                    //回溯，为另分一个分支接下来的递归设置条件，不是全部置空
                                    // visit[posX][posY] = 0;只要访问过的就不再访问                                 
                                    stack.pop();

                                }
                            }

                        }
                    }
            }
        }
    }
    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;
    }


}