文章目录

题目描述我的分析我的代码大神分析大神代码

---

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

我的分析

【用例没通过，只是分享思路，希望大家一起交流】 找规律：我们把方格看成是一个矩阵，矩阵最左下角的为(0,0)，那么矩阵最右上角的数位之和就为最大 举个例子： $$\left[\begin{array}{cccc}\left(0,7\right)& \left(1,7\right)& \left(2,7\right)& \left(3,7\right)\\ \left(0,6\right)& \left(1,6\right)& \left(2,6\right)& \left(3,6\right)\\ \left(0,5\right)& \left(1,5\right)& \left(2,5\right)& \left(3,5\right)\\ \left(0,4\right)& \left(1,4\right)& \left(2,4\right)& \left(3,4\right)\\ \left(0,3\right)& \left(1,3\right)& \left(2,3\right)& \left(3,3\right)\\ \left(0,2\right)& \left(1,2\right)& \left(2,2\right)& \left(3,2\right)\\ \left(0,1\right)& \left(1,1\right)& \left(2,1\right)& \left(3,1\right)\\ \left(0,0\right)& \left(1,0\right)& \left(2,0\right)& \left(3,0\right)\end{array}\right]$$

若k 大于 矩阵最右上角的值，说明矩阵中最大的数位之和都比k小，那么其他的也小于，所以机器人能到达矩阵的全部格子若k 小于 矩阵中最大的数位之和 大于 矩阵最长边数位之和的最小值（矩阵左上角），机器人所能到达的格子是矩阵左上角数位之和为k+1的全部格子再减1 ，在例子中，假设k=8，那么机器人所能到达的格子是以（2,7）为最右上角的全部格子再减去（2,7）若k 小于 矩阵最长边数位之和的最小值 大于 矩阵最短边的数位之和的最大值，机器人所能到达的格子是以最短边为边长的正方形再加上一个下三角矩阵，在例子中，假设k=4，机器人所能到达的格子就是以最短边为4，顶点为（3，0）的正方形矩阵再加上一个以最左下角位置为（0,3），由（0,4）（0,3）（1,3）所形成的下三角矩阵若k 小于 矩阵最短边的数位之和的最大值还要小，那么其实机器人能到达的格子就是由k来决定的，就是算一个上三角或者下三角，用等差数列求和公式，在例子中，假设k=2，机器人所能到达的格子是以最左下角位置为（0,0），由（0,2）（0,1）（1,1）（0,0）（1,0）（2,0）

我的代码

/** * 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动， * 每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 * 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。 * 但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？ */ public class Solution { public int movingCount(int threshold, int rows, int cols) { int min = Min(cols,rows); int max = Max(cols,rows); if (rows == 0 || cols == 0) return 0; if (threshold == 0) return 1;//这时已经排除了rows或cols为0的情况 if (threshold>((sumNum(rows-1)+sumNum(cols-1)))){ //若最右上角的数位之和小于threshold，说明最大的都比threshold小，那么其他的也小于 return rows*cols; } if (threshold<((sumNum(rows-1)+sumNum(cols-1)))&&(threshold>(Max(cols,rows)-1))){ //若threshold 小于 矩阵中最大的数位之和 大于 矩阵最长边数位之和的最小值（矩阵左上角） //最短边上的数位之和的最大值一定是（0，y）或(x,0) return ((threshold+1)-(Max(cols,rows)-1))*Max(cols,rows)-1; } if ((threshold>(Max(cols,rows)-1))&&(threshold<(Min(cols,rows)-1))){ return Min(cols,rows)*Min(cols,rows)+(((threshold-Min(cols,rows)+1)+1)*(threshold-Min(cols,rows)+1)/2); } if (threshold<(Min(cols,rows)-1)){ return (((threshold+1)+1)*(threshold+1)/2); } return 0; } //求两数最小值 public int Min(int a,int b){ if (a>b) return b; if (a<b) return a; else return a; } //求两数最大值 public int Max(int a ,int b){ if (a>b) return a; if (a<b) return b; else return a; } //求一个数的数位之和 public int sumNum(int x){ int n = x%10; x = x - n; int m = x/10; int sum = 0; sum = sum + n; while (m!=0){ sum = sum + m%10; m = m/10; } return sum; } }

我也找不到哪里错了，自己感觉逻辑还是对的，有没有大佬帮我纠正纠正，谢谢~

大神分析

这个方格也可以看出一个m*n的矩阵。同样在这个矩阵中，除边界上的格子之外其他格子都有四个相邻的格子。 　　机器人从坐标(0,0)开始移动。当它准备进入坐标为(i,j)的格子时，通过检查坐标的数位和来判断机器人是否能够进入。如果机器人能够进入坐标为(i,j)的格子，我们接着再判断它能否进入四个相邻的格子(i,j-1)、(i-1,j),(i,j+1)和(i+1,j)。

大神代码

public class Solution { private int sum; public int movingCount(int threshold, int rows, int cols) { sum = 0; boolean[][] vis = new boolean[rows][cols]; Solve(0,0,rows,cols,vis,threshold); return sum; } public void Solve(int x, int y, int rows, int cols, boolean[][] vis, int threshold){ if (x<0 || y<0 || x>=rows || y>=cols || vis[x][y] || ((numSum(x)+numSum(y))>threshold)){ return; } vis[x][y] = true; sum++; Solve(x+1, y, rows, cols, vis, threshold); Solve(x-1, y, rows, cols, vis, threshold); Solve(x, y+1, rows, cols, vis, threshold); Solve(x, y-1, rows, cols, vis, threshold); } public int numSum(int x){ int res = 0; while (x!=0){ res += x%10; x /=10; } return res; } }