LeetCode 剑指 Offer 13. 机器人的运动范围
原题链接
中等
作者:
orange0912
,
2022-02-16 14:23:30
,
所有人可见
,
阅读 246
先 预处理所有能踩的下标,必须下标之和<=k,然后dfs 右边和下方2个方向即可
class Solution {
public:
int n,m;
int x[2]={0,1},y[2]={1,0},ans=0;
vector<vector<int>> v;//v存储该节点是否能进入,1能0不能
vector<vector<int>> p;//p存储是否访问过,1为访问过,0没有
int movingCount(int _m, int _n, int k)
{
n=_n,m=_m;
v.assign(m,vector<int>(n,0));
p.assign(m,vector<int>(n,0));
//预处理,能进入的点,各位和<=k
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
int t=i,s=j,e=0;
while(t>0)
{
e+=t%10;
t/=10;
}
while(s>0)
{
e+=s%10;
s/=10;
}
if(e>k)
v[i][j]=0;
else
v[i][j]=1;
}
}
dfs(0,0);
return ans;
}
void dfs(int a,int b)
{
ans++;//答案加一
for(int i=0;i<2;i++)
{
int dx=a+x[i],dy=b+y[i];//算出新下标
//判断是否越界,能否访问和是否访问过
if(dx<m&&dx>=0&&dy<n&&dy>=0&&v[dx][dy]==1&&p[dx][dy]==0)
{
p[dx][dy]=1;//置为访问过
dfs(dx,dy);//往下深搜
}
}
}
};