原题来自牛客网剑指offer系列：链接

问题描述

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

如：k=5，m=10，n=10，最终答案为21。

解题思路

这道题和剑指offer另外一道矩阵中的路径有点相似，核心算法都是回溯法。

我的思路是用able矩阵记录所有可以进入的方格（值设为1代表可进入），用一个矩阵ans_arr记录所有能够达到的格子（值设为1代表能够达到），从（0，0）开始暴力dfs搜索，上下左右四个方向都要搜，如果某个方格已经visit过或者ans_arr值为1或者able值为0，就可以返回了。

最终在主函数记录ans_arr中有多少个1就是答案。

返回条件

前面提到如果某个方格已经visit过或者ans_arr值为1或者able值为0，就可以返回了。

即相当于满足下面三个条件之一即可返回：

1、曾经遍历过

2、这个格子已经找到答案，是可达的

3、这个格子不可进入

代码如下：

if(visit[x][y]||ans_arr[x][y]==1||!able[x][y])	return;

AC代码

运行时间：5ms

占用内存：1144k

class Solution {
public:int row;int col;vector<vector<int> > ans_arr,able;//计算行列坐标数位和int getsum(int i,int j){int sum=0;while(i){sum+=i%10;i/=10;}while(j){sum+=j%10;j/=10;}return sum;}//返回答案int movingCount(int threshold, int rows, int cols){int ans=0;row=rows;col=cols;vector<vector<int> > visit(rows);for(auto &i:visit)i.resize(cols,0);ans_arr=visit;able=visit;for(int i=0;i<able.size();i++)for(int j=0;j<able[i].size();j++){if(getsum(i,j)<=threshold)able[i][j]=1;}getans(visit,0,0,0);for(int i=0;i<ans_arr.size();i++)for(int j=0;j<ans_arr[i].size();j++){if(ans_arr[i][j]==1)ans++;}return ans;}//dfsvoid getans(vector<vector<int> > visit,int nowpos,int x,int y){if(visit[x][y]||ans_arr[x][y]==1||!able[x][y])	return;ans_arr[x][y]=1;visit[x][y]=1;if(y>=1)	//左getans(visit,nowpos+1,x,y-1);if(y<col-1)	//右getans(visit,nowpos+1,x,y+1);if(x>=1)	//上getans(visit,nowpos+1,x-1,y);if(x<row-1)	//下getans(visit,nowpos+1,x+1,y);return;}
};