php高级网站开发,安平县哪里做网站,一键识图找原图,网页制作流程步骤剑指offer原题13:机器人的运动范围 地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动#xff0c;它每次可以向左、右、上、下移动一格#xff0c;但不能进入行坐标和列坐标的数位之和大于k的格子。例如#xff0c;当k为18时,机器人能够进入方格(35,37),因为353… 剑指offer原题13:机器人的运动范围 地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动它每次可以向左、右、上、下移动一格但不能进入行坐标和列坐标的数位之和大于k的格子。例如当k为18时,机器人能够进入方格(35,37),因为353718。但它不能进入方格(35,38)因为353819。请问该机器人能够到达多少个格子? LeetCode原题https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/description/ class Solution {public int wardrobeFinishing(int m, int n, int cnt) {// ps:这是力扣题目有点不一样方向只有两个。int[][] dir new int[][]{{1, 0}, {0, 1}};boolean[][] vis new boolean[m][n];LinkedListPairInteger, Integer queue new LinkedList();queue.push(new Pair(0, 0));int res 0;while(queue.size() 0) {PairInteger, Integer pair queue.pollFirst();vis[pair.getKey()][pair.getValue()] true;res;for(int i 0; i 2; i) {int nextX pair.getKey() dir[i][0];int nextY pair.getValue() dir[i][1];if(nextX 0 nextX m nextY 0 nextY n !vis[nextX][nextY] digitalSum(nextX) digitalSum(nextY) cnt) {queue.push(new Pair(nextX, nextY));}}}return res;}private int digitalSum(int x) {int res 0;while(x 0) {res x % 10;x / 10;}return res;}
}时间复杂度O(NM)
空间复杂度O(NM)
