AcWing 24. 机器人的运动范围 DFS
原题链接
简单
作者:
dfbdberberb
,
2020-04-18 12:03:48
,
所有人可见
,
阅读 1211
C++ 代码
class Solution {
public:
int k;
int b,a;
int f[52][52];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int movingCount(int threshold, int rows, int cols)
{
memset(f,false,sizeof f);
b=cols,a=rows;
int res=0;
k=threshold;
return dfs(0,0);
}
int dfs(int y,int x)
{
if(x<0||x>=a||y<0||y>=b||f[y][x]) return 0;
f[y][x]=true;
int res=0;
int x1=x,y1=y;
while(x1)
{
res+=(x1%10);
x1/=10;
}
while(y1)
{
res+=(y1%10);
y1/=10;
}
if(res>k) return 0;
int sum=0;
for(int i=0;i<4;i++)
{
int q=x+dx[i],p=y+dy[i];
sum+=dfs(p,q);
}
return sum+1;
}
};