脚本宝典收集整理的这篇文章主要介绍了【数据结构】Robot area 机器人运动范围，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

Robot area 机器人运动范围

有一个 m*n的矩阵，从【0,0】到【m-1,n-1】。机器人从【0,0】开始移动，每一次可以上下左右移动一格。不能出界，也不能进入行坐标与列坐标数字之和大于k的格子。计算机器人能到达多少个格子。

in：m = 2, n = 3, k = 1
out：6
in：m = 3, n = 1, k = 0
out：1

思路

使用BFS，借助方向数组处理，移动的坐标扩展。扩展后计算坐标是否合法，是否sum<=k

因为记录的是到达的格子数，也就是说，统计出所有能被BFS到的坐标点

 public int movingCount(int m, int n, int k) {
        if(k==0){
            return 1;
        }
        int[] dum = new int[100];
        for (int i = 0; i <10 ; i++) {
            for (int j = 0; j < 10; j++) {
                dum[i*10+j]=i+j;
            }
        }
        HashSet<Integer> set = new HashSet<>();
 
        Queue<int[]> queue = new LinkedList<int[]>();
        int ans = 0;
        set.add(0);
        queue.offer(new int[]{0,0});
        int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
        while(!queue.iSEMpty()){
            int[] tmp = queue.PEek();
            ans++;
            for(int d = 0;d<4;d++ ){
                int x = tmp[0]+dir[d][0];
                int y = tmp[1]+dir[d][1];
                if(x<0||x>;m-1){
                    continue;
                }
                if(y<0||y>n-1){
                    continue;
                }
                if(set.contains(x*n+y)){
                    continue;
                }
                if(dum[x]+dum[y]>k){
                    continue;
                }
                set.add(x*n+y);
                queue.offer(new int[]{x,y});
            }
            queue.poll();
        }
        return ans;

    }

Tag

BFS

脚本宝典总结

以上是脚本宝典为你收集整理的【数据结构】Robot area 机器人运动范围全部内容，希望文章能够帮你解决【数据结构】Robot area 机器人运动范围所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。