地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如,当 threshold 为 18 时,机器人能够进入方格 [35,37] ,因为 3+5+3+7 = 18。但是,它不能进入方格 [35,38] ,因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子?
1条回答 默认 最新
关注
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; } };
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报