[bfs][dfs]剑指 Offer 13. 机器人的运动范围(medium)

机器人的运动范围(medium)"/>

[bfs][dfs]剑指 Offer 13. 机器人的运动范围(medium)

题目：

题解：

bfs dfs 纯模板题。

代码如下：

// 四个方向数组
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
// 标记数组，防止点重复访问
bool visited[110][110];using PII = pair<int,int>;class Solution {
public:// 题解1：dfsint movingCount_1(int m, int n, int k) {memset(visited,0,sizeof visited);int cnt=0;dfs(m,n,k,0,0,cnt);return cnt;}// 题解2：bfsint movingCount(int m,int n,int k){memset(visited,0,sizeof visited);int cnt=0;queue<PII> q;q.push({0,0});visited[0][0]=1;// 进行bfswhile(!q.empty()){auto [i,j]=q.front();q.pop();cnt++;// 进行4个方向的bfsfor(int c=0;c<4;++c){int x=i+dx[c],y=j+dy[c];// 历史和实现告诉我们进队就要打标记if(x>=0&&x<m&&y>=0&&y<n&&!visited[x][y]&&(work(x)+work(y)<=k)){visited[x][y]=1;q.push({x,y});}}}return cnt;}void dfs(int m,int n,int k,int i,int j,int& cnt){// 无法到达(i,j)这个点if(work(i)+work(j)>k)return;// 可以到(i,j)这个点，则打标记和cnt+1visited[i][j]=true;   cnt++;// 进行4个方向的dfsfor(int c=0;c<4;++c){int x=i+dx[c],y=j+dy[c];if(x>=0&&x<m&&y>=0&&y<n&&!visited[x][y])dfs(m,n,k,x,y,cnt);}}// 计算各数位之和int work(int x){int val=0;while(x)val+=x%10,x/=10;return val;}
};