题目
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
思路 + 代码
回溯方法,类似题目1、题目2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| public class Solution { private int k; private int res; private int[][] next = new int[][]{{0,1},{0,-1},{1,0},{-1,0}}; public int movingCount(int threshold, int rows, int cols) { if(rows<=0 || cols<=0 || threshold<0) return 0; k = threshold; res = 0; boolean[][] visit = new boolean[rows][cols]; dfs(0,0, visit); return res; } private void dfs(int i, int j, boolean[][] visit){ if(i<0 || j<0 || i>=visit.length || j>=visit[0].length || k<calNum(i)+calNum(j) || visit[i][j] ){ return; } res++; visit[i][j] = true; for(int[] step: next){ dfs(i+step[0], j+step[1], visit); } return; } private int calNum(int num){ int res = 0; while(num > 0){ res += num%10; num /= 10; } return res; } }
|