AcWing 24：机器人的运动范围 ← BFS、DFS

【题目来源】
https://www.acwing.com/problem/content/description/22/

【题目描述】
地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请依次输入k，m，n，问该机器人能够达到多少个格子？
注意：0<=m<=50，0<=n<=50，0<=k<=100

【算法分析】
◆DFS算法模板：https://blog.csdn.net/hnjzsyjyj/article/details/125801217

void dfs(int step){判断边界{输出解 }尝试每一种可能{满足check条件{标记继续下一步：dfs(step+1)恢复初始状态（回溯的时候要用到）}}
}

◆BFS算法模板：https://blog.csdn.net/hnjzsyjyj/article/details/118736059

助记：建-入-量：头-出-入”。其中，“建-入-量：头-出-入”各字的解析如下：
建：建队
入：入队
量：队中元素个数。作为while循环的条件。
头：队头
出：出队
入：入队

一个记忆场景，“小猫咪在建好的洞口，想入洞。先用胡子量过洞口大小后，然后用头出入洞”。

【算法代码：DFS】

#include <bits/stdc++.h>
using namespace std;const int maxn=105;
int flag[maxn][maxn];
int sum=0;int dfs(int x,int y,int k,int m,int n) {if(flag[x][y]==1 || x>=m || y>=n || (x/10+x%10+y/10+y%10)>k) return 0;flag[x][y]=1;sum=dfs(x+1,y,k,m,n)+dfs(x,y+1,k,m,n)+1;return sum;
}int movingCount(int k,int m,int n){for(int i=0;i<m;i++){for(int j=0;j<n;j++){flag[i][j]=0;}}return dfs(0,0,k,m,n);
}int main(){int k,m,n;cin>>k>>m>>n;cout<<movingCount(k,m,n)<<endl;return 0;
}/*
in:5 0 0
out:0in:7 4 5
out:20in:18 40 40
out:1484
*/

【算法代码：BFS】

#include <bits/stdc++.h>
using namespace std;const int maxn=105;
int flag[maxn][maxn];
int sum=0;int movingCount(int k,int m,int n) {if(m==0 || n==0) return 0; //very importantfor(int i=0; i<m; i++) {for(int j=0; j<n; j++) {flag[i][j]=0;}}queue<pair<int,int>> q;q.push({0,0});flag[0][0]=1;int dx[]= {0,0,-1,1};int dy[]= {-1,1,0,0};while(!q.empty()) {auto t=q.front(); //pair<int,int> t=q.front();q.pop();int x=t.first;int y=t.second;sum++;for(int i=0; i<4; i++) {int nx=x+dx[i];int ny=y+dy[i];if(nx<0 || ny<0) continue;if(flag[nx][ny]==1 || nx>=m || ny>=n || (nx/10+nx%10+ny/10+ny%10)>k) continue;q.push({nx,ny});flag[nx][ny]=1;}}return sum;
}int main() {int k,m,n;cin>>k>>m>>n;cout<<movingCount(k,m,n)<<endl;return 0;
}/*
in:5 0 0
out:0in:7 4 5
out:20in:18 40 40
out:1484
*/

【参考文献】
https://blog.csdn.net/qq_40184885/article/details/89483505
https://www.cnblogs.com/wzw0625/p/12731031.html