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

机器人的运动范围

https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8

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


}

全部评论

相关推荐

Twilight_m...:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
投递美团等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务