[编程题]机器人的运动范围

```class Solution:
def __init__(self):
self.count = 0

def movingCount(self, threshold, rows, cols):
# write code here
arr = [[1 for i in range(cols)] for j in range(rows)]
self.findway(arr, 0, 0, threshold)
return self.count

def findway(self, arr, i, j, k):
if i < 0 or j < 0 or i >= len(arr) or j >= len(arr[0]):
return
tmpi = list(map(int, list(str(i))))
tmpj = list(map(int, list(str(j))))
if sum(tmpi) + sum(tmpj) > k or arr[i][j] != 1:
return
arr[i][j] = 0
self.count += 1
self.findway(arr, i + 1, j, k)
self.findway(arr, i - 1, j, k)
self.findway(arr, i, j + 1, k)
self.findway(arr, i, j - 1, k)
```

```public class Solution {

public int movingCount(int threshold, int rows, int cols) {
int flag[][] = new int[rows][cols]; //记录是否已经走过
return helper(0, 0, rows, cols, flag, threshold);
}

private int helper(int i, int j, int rows, int cols, int[][] flag, int threshold) {
if (i < 0 || i >= rows || j < 0 || j >= cols || numSum(i) + numSum(j)  > threshold || flag[i][j] == 1) return 0;
flag[i][j] = 1;
return helper(i - 1, j, rows, cols, flag, threshold)
+ helper(i + 1, j, rows, cols, flag, threshold)
+ helper(i, j - 1, rows, cols, flag, threshold)
+ helper(i, j + 1, rows, cols, flag, threshold)
+ 1;
}

private int numSum(int i) {
int sum = 0;
do{
sum += i%10;
}while((i = i/10) > 0);
return sum;
}
}```

/**
@author zhengyanan
@date 2017/3/14 @time 17:09
version_3:回溯法

1.从(0,0)开始走，每成功走一步标记当前位置为true,然后从当前位置往四个方向探索，

2.探索时，判断当前节点是否可达的标准为：
1）当前节点在矩阵内；
2）当前节点未被访问过；
3）当前节点满足limit限制。
3.

*/
```    public int movingCount(int threshold, int rows, int cols) {
boolean[][] visited = new boolean[rows][cols];
return countingSteps(threshold,rows,cols,0,0,visited);
}
public int countingSteps(int limit,int rows,int cols,int r,int c,boolean[][] visited){
if (r < 0 || r >= rows || c < 0 || c >= cols
|| visited[r][c] || bitSum(r) + bitSum(c) > limit)  return 0;
visited[r][c] = true;
return countingSteps(limit,rows,cols,r - 1,c,visited)
+ countingSteps(limit,rows,cols,r,c - 1,visited)
+ countingSteps(limit,rows,cols,r + 1,c,visited)
+ countingSteps(limit,rows,cols,r,c + 1,visited)
+ 1;
}
public int bitSum(int t){
int count = 0;
while (t != 0){
count += t % 10;
t /= 10;
}
return  count;
}```
/**
@author zhengyanan
@date 2017/3/14 @time 16:26
version_2:（此段代码有问题）

1.本来想的是遍历每一行，找到右端第一个不能到达的点，以此为界，此界点前的点都可以到达，之后的点

2.但后来发现，这种思路有问题，机器人可以通过上一行或者下一行的格子进入此行界点之后的格子。

*/
```//    public int movingCount(int threshold, int rows, int cols){
//        int r,cMax, rSum,cSumMax;
//        int count = 0;
//        for (int i = 0; i < rows; i++) {
//            rSum = 0;
//            r = i;
//            while (r != 0){
//                rSum += r % 10;
//                r /= 10;
//            }
//            cSumMax = threshold - rSum;
//
//            if (cSumMax < 0)    break;
//            else{
//                numberOfNine = cSumMax / 9;
//                add = cSumMax % 9;
//                max = add + 1;
//                if (numberOfNine > 0){
//                    max = max * 10 + 9;
//                    numberOfNine--;
//                }
//                count += max < cols ? max : cols;
//                System.out.println(i+";"+(max < cols? max:cols));
//            }
//        }
//        return count;
//    }```
/**
@author zhengyanan
@date 2017/3/13 @time 16:48
version_1:（此段代码有问题）

1.判断threshold 和 rows、cols 的关系，分情况讨论
(PS:题意理解错误！！！原题应该是各数位之和，而不是 行数和列数的和。)
*/
```//    public int movingCount(int threshold, int rows, int cols){
//        int smaller,bigger,result;
//        smaller = rows <= cols ? rows:cols;
//        bigger = rows + cols - smaller;
//
//        result = (threshold + 1) * (threshold + 1 + 1) / 2;
//        if (threshold <= smaller){
//
//        }
//        else if (threshold > smaller && threshold <= bigger){
//            int t, differ = threshold - smaller;
//            t = differ * (1 + differ) / 2;
//            result -= t;
//        }
//        else {
//            int t = 0,differ1,differ2;
//            differ1 = threshold - smaller;
//            differ2 = threshold - bigger;
//            t += differ1 * (1 + differ1) / 2;
//            t += differ2 * (1 + differ2) / 2;
//
//            result -= t;
//        }
//        return result;
//    }```

```//思路：dfs,搜索四个方向，vis记录该方格是否被搜索过，
// 预判方格是否合法，合法就从该方格接着搜索  ```
```const int MAXN=100;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};    //四个方向
int vis[MAXN][MAXN]={0};    //记录数组
int sum;    //记录结果

class Solution {
public:
void dfs(int x,int y,int k,int m,int n)
{
vis[x][y]=1;
for(int i=0;i<=3;++i)
{
int newx=x+dx[i],newy=y+dy[i];
//预判方格是否合法，合法就从该方格接着搜索
if(vis[newx][newy]==0&&newx>=0&&newx<m&&newy>=0&&newy<n&&(newx%10+newx/10+newy%10+newy/10<=k))
{
++sum;
dfs(newx,newy,k,m,n);
}
}
}
int movingCount(int k, int rows, int cols)
{
if(k<0)
return 0;
memset(vis,0,sizeof(vis));
sum=1;
dfs(0,0,k,rows,cols);
return sum;

}
};```

```class Solution {
public:
int movingCount(int threshold, int rows, int cols)
{
bool* flag=new bool[rows*cols];
for(int i=0;i<rows*cols;i++)
flag[i]=false;
int count=moving(threshold,rows,cols,0,0,flag);//从（0,0）坐标开始访问;
delete[] flag;
return count;
}
//计算最大移动位置
int moving(int threshold,int rows,int cols,int i,int j,bool* flag)
{
int count=0;
if(check(threshold,rows,cols,i,j,flag))
{
flag[i*cols+j]=true;
//标记访问过，这个标志flag不需要回溯，因为只要被访问过即可。
//因为如果能访问，访问过会加1.不能访问，也会标记下访问过。
count=1+moving(threshold,rows,cols,i-1,j,flag)
+moving(threshold,rows,cols,i,j-1,flag)
+moving(threshold,rows,cols,i+1,j,flag)
+moving(threshold,rows,cols,i,j+1,flag);
}
return count;
}
//检查当前位置是否可以访问
bool check(int threshold,int rows,int cols,int i,int j,bool* flag)
{
if(i>=0 && i<rows && j>=0 && j<cols
&& getSum(i)+getSum(j)<=threshold
&& flag[i*cols+j]==false)
return true;
return false;
}
//计算位置的数值
int getSum(int number)
{
int sum=0;
while(number>0)
{
sum+=number%10;
number/=10;
}
return sum;
}
};```

```动态规划 dp[i][j]表示是否可以到达，统计数字中true的个数，即为可以到达的格子数
public class Solution {
public int movingCount(int threshold, int rows, int cols)
{
if(threshold<0)
return 0;
boolean [][] dp=new boolean[rows+1][cols+1];
dp[0][0]=true;
for(int i=1;i<=rows;i++){//初始化
if(dp[i-1][0]&&canreach(threshold,i,0)){
dp[i][0]=true;
}else {
dp[i][0]=false;
}
}
for(int i=1;i<=cols;i++){//初始化
if(dp[0][i-1]&&canreach(threshold,0,i)){
dp[0][i]=true;
}else {
dp[0][i]=false;
}
}
for(int i=1;i<=rows;i++){
for(int j=1;j<=cols;j++){
if((dp[i-1][j]&&canreach(threshold, i, j))||(dp[i][j-1]&&canreach(threshold, i, j))){
dp[i][j]=true;
}else {
dp[i][j]=false;
}
}
}
int count=0;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(dp[i][j])
count++;
}
}
return count;
}
public  boolean canreach(int threshold, int x, int y) {
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
while (y > 0) {
sum += y % 10;
y /= 10;
}
return sum <= threshold;
}
}```

DFS
```class Solution {
bool canreach(int threshold, int x, int y) {
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
while (y > 0) {
sum += y % 10;
y /= 10;
}
return sum <= threshold;
}
public:
int movingCount(int threshold, int rows, int cols)
{
vector<vector<bool>> grid(rows);
for (auto& row : grid) {
row.resize(cols, false);
}
queue<pair<int, int>> que;
if (canreach(threshold, 0, 0)) {
que.push(make_pair(0, 0));
grid[0][0] = true;
}
int cnt = 0;
while (!que.empty()) {
++cnt;
int x, y;
tie(x, y) = que.front();
que.pop();
if (x + 1 < rows && !grid[x + 1][y] && canreach(threshold, x + 1, y)) {
grid[x + 1][y] = true;
que.push(make_pair(x + 1, y));
}
if (y + 1 < cols && !grid[x][y + 1] && canreach(threshold, x, y + 1)) {
grid[x][y + 1] = true;
que.push(make_pair(x, y + 1));
}
}
return cnt;
}
};
```

```public class Solution {

/**算法本质：
* DFS||BFS 寻找连通分量
*
* 题目分析：
* 机器人在一个矩阵上的m*n个格子上移动，可进入的格子的集合可抽象为以下点集：
* { (row, col) | (i%10+i/10+j%10+j/10) <= threshold }。且路径节点可重复，无步数限制。
* 问：机器人能到达多少个格子？
*
* 题目抽象：
* 倘若我们把矩阵的每一个“格子”抽象成一个“结点”，把“格子相邻”抽象为“结点连通”（结点之间存在无向边），
* 把“无法进入的格子”抽象成“与所有普通结点都不连通（不存在无向边）的孤点”，则整个问题可以抽象为：
* 从某个结点出发，寻找无向图的连通分量的节点个数。很显然，可以使用DFS或者BFS进行实现
*
* 算法实现：
* 这里选择DFS进行实现。
* 设置两个辅助boolean矩阵：visited与isWall。前者是DFS中的典型辅助矩阵，记录每个节点是否已访问过。
* 后者用来表示每个节点是否是不能进入的“孤点”。
* 设置静态变量nodeCnt，用于在DFS的过程中记录访问过的结点数
* DFS递归函数的出口条件设置为：
* (outOfBoundary(rows, cols, row, col) || visited[row][col] || isWall[row][col] )
* 即：“若超过边界（到矩阵之外）”或“访问过”或“是无法进入的结点” 则 return
* 然后进行DFS。
* */

int nodeCnt = 0;
boolean[][] visited;
boolean[][] isWall;
int threshold;
int rows;
int cols;

public int movingCount(int threshold, int rows, int cols){
if (threshold<0 || rows<=0 || cols<=0) //robust
return 0;//牛客示例是0

//init
this.nodeCnt = 0;
this.threshold = threshold;
this.rows = rows;
this.cols = cols;
this.visited = new boolean[rows][cols];
this.isWall = new boolean[rows][cols];
for (int i=0;i<rows;i++){
for (int j=0;j<cols;j++){
this.visited[i][j]=false;
if ( (i%10+i/10+j%10+j/10) > threshold )
this.isWall[i][j]=true;
else
this.isWall[i][j]=false;
}
}

//body
DFS(0,0);
return this.nodeCnt;
}

public void DFS(int row, int col){
if (   outOfBoundary(rows, cols, row, col)
|| visited[row][col]
|| isWall[row][col] )
return;

//visit
visited[row][col]=true;
nodeCnt++;

//DFS
DFS(row+1, col);
DFS(row-1, col);
DFS(row, col+1);
DFS(row, col-1);
}

public boolean outOfBoundary(int rows, int cols, int row, int col){
return ( row<0 || row>=rows || col<0 || col>=cols );
}

}```

```//java简单易懂版
public class Solution {
int count=0;
public int movingCount(int threshold, int rows, int cols)
{
boolean[] pass = new boolean[rows*cols];
movingCount(threshold,0,0,rows,cols,pass);
return count;
}
public void movingCount(int threshold, int i, int j,int rows, int cols,boolean[] pass){
int index = i*cols+j;
if(i<0||j<0||i>=rows||j>=cols||pass[index]==true)
return ;
if(helper(i,j)<=threshold){
count++;
pass[index]=true;
}else{
pass[index]=false;
return;
}
movingCount(threshold, i-1, j,rows,  cols,pass);
movingCount(threshold, i+1, j,rows,  cols,pass);
movingCount(threshold, i, j-1,rows,  cols,pass);
movingCount(threshold, i, j+1,rows,  cols,pass);
}
public int helper(int i,int j){
int sum = 0;
do{
sum += i%10;
}while((i = i/10) > 0);

do{
sum += j%10;
}while((j = j/10) > 0);
return sum;
}
}
```

# python solution:

``````class Solution:
def movingCount(self, threshold, rows, cols):
self.row, self.col = rows, cols
self.dict = set()
self.search(threshold, 0, 0)
return len(self.dict)

def judge(self, threshold, i, j):
return sum(map(int, list(str(i)))) + sum(map(int, list(str(j)))) <= threshold

def search(self, threshold, i, j):
if not self.judge(threshold, i, j) or (i, j) in self.dict:
return
if i != self.row - 1:
self.search(threshold, i + 1, j)
if j != self.col - 1:
self.search(threshold, i, j + 1)
``````

## 如果不加这一句，时间复杂度不会满足。

```public class Solution {

public int movingCount(int threshold, int rows, int cols) {
int[][] flag = new int[rows][cols];
return moving(threshold, rows, cols, flag, 0, 0);
}

public int moving(int threshold, int rows, int cols, int[][] flag, int i, int j){
if(threshold <= 0 || i >= rows || i< 0 || j >= cols || j < 0 || (flag[i][j] == 1) || (sum(i) + sum(j) > threshold)){
return 0;
}
flag[i][j] = 1;
return moving(threshold, rows, cols, flag, i - 1, j)
+moving(threshold, rows, cols, flag, i + 1, j)
+moving(threshold, rows, cols, flag, i, j - 1)
+moving(threshold, rows, cols, flag, i, j + 1)
+ 1;
}

public int sum(int i ){
if(i == 0){return i ;}
int sum = 0;
while(i != 0){
sum += i % 10;
i /= 10;
}
return sum;
}

}```

【java】和上一题类似，本题依然用DFS来解题，依然提供递归和非递归两种方法，了解一下！

1.需要记录已经遍历过的节点，用辅助矩阵visited[rows * cols]
2.每次加入时，count++标记已经遍历，这样下一个节点就不会遍历了

1.每一位的和小于等于threshold
2.x和 y  的边界条件
3.没有遍历过
``` public int movingCount(int threshold, int rows, int cols)
{
if(rows <= 0 || cols <= 0 || threshold < 0) return 0;
Stack<Integer> s = new Stack<>();
boolean[] visited = new boolean[rows * cols];
int[][] xoy = {{0,1,0,-1},{1,0,-1,0}};
int count = 0;
visited[0] = true;
while(!s.empty()) {
int  cur = s.pop();
count++;
for (int i = 0; i < 4; i++) {
int x = cur % cols + xoy[0][i];
int y = cur / cols + xoy[1][i];
int sum = getDigitSum(x) + getDigitSum(y);
if(x >= 0 && x < cols && y >= 0 && y < rows
&& sum <= threshold && !visited[x + y * cols]) {
visited[x + y * cols] = true;
}
}
}
return count;
}

private int getDigitSum(int i) {//获取位的和
int sum = 0;
while(i > 0) {
sum += i % 10;
i /= 10;
}
return sum;
}
```

* 递归的方式更加简单了，比上一题简单
* 出口：
*    0:不满足边界条件 ；已经遍历过；位数和大于阈值
* 1.递：
*     1.1标记遍历
*     1.2上下左右递归
* 2.归：返回count
``` public int movingCount(int threshold, int rows, int cols)
{
if(rows <= 0 || cols <= 0 || threshold < 0) return 0;
boolean[] visited = new boolean[rows * cols];
return dfs(threshold,rows,cols,visited,0,0);
}
private  int dfs(int threshold, int rows, int cols, boolean[] visited, int x, int y) {
if(x < 0 || x >= cols || y < 0 || y >= rows
|| getDigitSum(x) + getDigitSum(y) > threshold || visited[x + y * cols])
return 0;//出口
visited[x + y * cols] = true;//标记
return 1 + dfs(threshold, rows, cols, visited, x, y - 1)//归
+ dfs(threshold, rows, cols, visited, x + 1, y)
+ dfs(threshold, rows, cols, visited, x, y + 1)
+ dfs(threshold, rows, cols, visited, x - 1, y);
}
private int getDigitSum(int i) {
int sum = 0;
while(i > 0) {
sum += i % 10;
i /= 10;
}
return sum;
}

```

``````class Solution {
public:

bool if_ok(int x, int y, int th){
int sum = 0;
string sx = to_string(x);
string sy = to_string(y);
for(int i = 0; i < sx.length();i++) sum += sx[i]-'0';
for(int i = 0; i < sy.length();i++) sum += sy[i]-'0';
return sum <= th;
}

int movingCount(int threshold, int rows, int cols){
if(threshold <= 0) return 0;
int stepx[4] = {1, -1, 0, 0};
int stepy[4] = {0, 0, 1, -1};
vector<vector<int> > dp(rows, vector<int>(cols, 0));
queue<int> qx; queue<int> qy;
qx.push(0); qy.push(0); dp[0][0] = 1;
int ans = 0;
while(!qx.empty()){
ans++;
int x = qx.front(); qx.pop();
int y = qy.front(); qy.pop();
for(int i = 0; i < 4; i++){
if(x+stepx[i]<rows && x+stepx[i]>=0 &&
y+stepy[i]<cols && y+stepy[i]>=0 &&
if_ok(x+stepx[i],y+stepy[i],threshold) &&
dp[x+stepx[i]][y+stepy[i]] == 0){
qx.push(x+stepx[i]);
qy.push(y+stepy[i]);
dp[x+stepx[i]][y+stepy[i]] = 1;
}
}
}
return ans;
}
};
``````

1、单行或者单列，一旦坐标数位之和小于k，之后的格子就走不到了，返回结果。
2、只要行列数大于等于2，除了不符合要求的格子，其他的都能访问到
``` class Solution {
public:
int movingCount(int threshold, int rows, int cols)
{
int res = 0;
for (int i = 0; i < rows; ++i)
for (int j = 0; j < cols; ++j)
if (!bigger(threshold, i, j))
++res;
else if (rows == 1 || cols == 1)
return res;
return res;
}
bool bigger(int num, int m, int n) {
int sum = 0;
while (m) {
sum += m % 10;
m /= 10;
}
while (n) {
sum += n % 10;
n /= 10;
}
return (num < sum);
}
};
```

# python solution:

```class Solution:
def getDigitSum(self,number):
return sum(map(int,list(str(number))))
def check(self,threshold,rows,cols,row,col,visited):
if row>=0 and row<rows and col>=0 and col<cols and self.getDigitSum(row)+self.getDigitSum(col)<=threshold and not (row,col) in visited:
return True
return False
def movingCountCore(self,threshold, rows, cols, row, col, visited):
count=0
if self.check(threshold,rows,cols,row,col,visited):
count=1+self.movingCountCore(threshold,rows,cols,row-1,col,visited)+self.movingCountCore(threshold,rows,cols,row,col-1,visited)+self.movingCountCore(threshold,rows,cols,row+1,col,visited)+self.movingCountCore(threshold,rows,cols,row,col+1,visited)
return count
def movingCount(self,threshold, rows, cols):
# write code here
if threshold<0 or rows<=0 or cols<=0:
return 0
visited=set()
count=self.movingCountCore(threshold,rows,cols,0,0,visited)
return count```

```function movingCount(threshold, rows, cols)
{
// write code here
if(!threshold)return 1;
if(!rows||!cols)return 0;
var visited = [];
var temp = [];
var i, j;
var count = {count:0};
for (i = 0; i < rows; i++) {
temp = [];
for (j = 0; j < cols; j++) {
temp.push(false);
}
visited.push(temp);
}
move(threshold, rows, cols, 0, 0, count, visited);
return count.count;
}

function move(threshold, rows, cols, row, col, count, visited) {
var isMove = false;
if(rows>row&&cols>col&&col>=0&&row>=0&&!visited[row][col]) {
if(bitSum(row) + bitSum(col) <= threshold) {
visited[row][col] = true;
count.count++;
move(threshold, rows, cols, row+1, col, count, visited);
move(threshold, rows, cols, row-1, col, count, visited);
move(threshold, rows, cols, row, col-1, count, visited);
move(threshold, rows, cols, row, col+1, count, visited);
}
}
return isMove;
}

function bitSum(num) {
var sum = 0;
while(num) {
sum+=num%10;
num = parseInt(num/10)
}
return sum;
}

module.exports = {
movingCount : movingCount
};```

```//回溯法。仔细审题。。。
class Solution {
public:
int movingCount(int threshold, int rows, int cols) {
int res = 0;
bool* flag = new bool[rows*cols];
memset(flag, 0, rows*cols);
dfs(threshold, rows, cols, flag, 0, 0, res);
return res;
}
void dfs(int threshold, int rows, int cols, bool* flag, int i, int j, int &res) {
if (i<0 || i >= rows || j<0 || j >= cols)
return;
if (*(flag + i*cols + j) == 1)
return;
if (check(i,j,threshold)){
res++;
*(flag + i*cols + j) = 1;
dfs(threshold, rows, cols, flag, i, j - 1, res);//左
dfs(threshold, rows, cols, flag, i, j + 1, res);//右
dfs(threshold, rows, cols, flag, i - 1, j, res);//上
dfs(threshold, rows, cols, flag, i + 1, j, res);//下
}
}
bool check(int ii,int jj,int threshold){
int sum = 0;
while (ii != 0) {
sum += ii % 10;
ii = ii / 10;
}
while (jj != 0) {
sum += jj % 10;
jj = jj / 10;
}
return sum<=threshold;
}
};```

```//非递归，利用栈实现
class Solution {
public:
int Count(int row, int col){
int count=0;
while(row||col){
count+=row%10+col%10;
row/=10;
col/=10;
}
return count;
}
int movingCount(int threshold, int rows, int cols){
if((rows<1&&cols<1)||threshold<0)
return 0;
int R=1;
bool* visited=new bool[rows*cols];
memset(visited,0,rows*cols);
visited[0]=true;
stack<int> S;
S.push(0);
int p[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
while(!S.empty()){
int i=S.top()/cols,j=S.top()%cols;
S.pop();
for(int k=0;k<4;k++){
int row=i+p[k][0],col=j+p[k][1];
if(row>=0&&row<rows&&col>=0&&col<cols&&!visited[row*cols+col]&&Count(row,col)<=threshold){
S.push(row*cols+col);
visited[row*cols+col]=true;
R++;
}
}
}
return R;
}
};```

```import java.util.*;
public class Solution {
ArrayList<Integer> result = new ArrayList<Integer>();
public int movingCount(int threshold, int rows, int cols)
{
int len = rows*cols;
int[] state= new int[len];
return core(threshold,0,0,state,0,rows,cols);

}
public int core(int k,int i,int j ,int[] state,int step,int rows,int cols){
int count = 0;
if(canIn(k,i,j ,state,step,rows,cols)){
state[i*cols+j]=1;
count = 1+core(k,i+1,j ,state,step,rows,cols)+core(k,i-1,j ,state,step,rows,cols)+
core(k,i,j+1 ,state,step,rows,cols)+core(k,i,j-1 ,state,step,rows,cols);
}
return count;
}
public boolean canIn(int k,int i,int j ,int[] state,int step,int rows,int cols){
int index = cols*i+j;
if(i>=0&&j>=0&&i<rows&&j<cols&&state[index]!=1&&getSum(i,j)<=k){return true;}
return false;
}
public int getSum(int i ,int j ){
int sum = 0;
while(i>0){
sum+=i%10;
i/=10;
}
while(j>0){
sum+=j%10;
j/=10;
}
return sum;
}
}```

```/*

*/
class Assist{
constructor(rows,cols){
this.visited = new Array(rows*cols);
this.visited.fill(false);
}
}
function movingCount(threshold, rows, cols)
{
let assist = new Assist(rows,cols);
let count = movingCountCore(threshold,rows,cols,0,0,assist);
assist = null;
return count;
}

function movingCountCore(threshold,rows,cols,row,col,assist) {
let count = 0;
if(check(threshold,rows,cols,row,col,assist)){
assist.visited[row*cols+col] = true;
count = 1+ movingCountCore(threshold,rows,cols,row-1,col,assist)
+ movingCountCore(threshold,rows,cols,row,col-1,assist)
+ movingCountCore(threshold,rows,cols,row+1,col,assist)
+ movingCountCore(threshold,rows,cols,row,col+1,assist);
}
return count;
}
function check(threshold,rows,cols,row,col,assist) {
if(row>=0 && row < rows && col>=0 && col<cols && getDigitSum(row)+getDigitSum(col) <= threshold
&& !assist.visited[row*cols+col]){
return true;
}
return false;
}

function getDigitSum(num) {
let sum = 0;
while (num>0){
sum+= num%10;
num = parseInt(num/10);
}
return sum;
}```

645条回答 58581浏览

# 通过挑战的用户

• 2019-10-17 00:36:07
• 2019-10-17 00:01:54
• 2019-10-16 23:39:27
• 2019-10-16 22:45:18
• 2019-10-16 22:30:44

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题