什么是网站设计与运营,商业收款码怎么推广赚钱,网站建设关于,网站建设新闻动态【题目来源】https://www.acwing.com/problem/content/description/22/【题目描述】 地上有一个 m 行和 n 列的方格#xff0c;横纵坐标范围分别是 0∼m−1 和 0∼n−1。 一个机器人从坐标 (0,0) 的格子开始移动#xff0c;每一次只能向左#xff0c;右#xff0c;上#…【题目来源】https://www.acwing.com/problem/content/description/22/【题目描述】 地上有一个 m 行和 n 列的方格横纵坐标范围分别是 0∼m−1 和 0∼n−1。 一个机器人从坐标 (0,0) 的格子开始移动每一次只能向左右上下四个方向移动一格。 但是不能进入行坐标和列坐标的数位之和大于 k 的格子。 请依次输入kmn问该机器人能够达到多少个格子注意0m500n500k100【算法分析】◆DFS算法模板https://blog.csdn.net/hnjzsyjyj/article/details/125801217
void dfs(int step){判断边界{输出解 }尝试每一种可能{满足check条件{标记继续下一步dfs(step1)恢复初始状态回溯的时候要用到}}
}
◆BFS算法模板https://blog.csdn.net/hnjzsyjyj/article/details/118736059
助记建-入-量头-出-入”。其中“建-入-量头-出-入”各字的解析如下
建建队
入入队
量队中元素个数。作为while循环的条件。
头队头
出出队
入入队
一个记忆场景“小猫咪在建好的洞口想入洞。先用胡子量过洞口大小后然后用头出入洞”。 【算法代码DFS】
#include bits/stdc.h
using namespace std;const int maxn105;
int flag[maxn][maxn];
int sum0;int dfs(int x,int y,int k,int m,int n) {if(flag[x][y]1 || xm || yn || (x/10x%10y/10y%10)k) return 0;flag[x][y]1;sumdfs(x1,y,k,m,n)dfs(x,y1,k,m,n)1;return sum;
}int movingCount(int k,int m,int n){for(int i0;im;i){for(int j0;jn;j){flag[i][j]0;}}return dfs(0,0,k,m,n);
}int main(){int k,m,n;cinkmn;coutmovingCount(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 maxn105;
int flag[maxn][maxn];
int sum0;int movingCount(int k,int m,int n) {if(m0 || n0) return 0; //very importantfor(int i0; im; i) {for(int j0; jn; j) {flag[i][j]0;}}queuepairint,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 tq.front(); //pairint,int tq.front();q.pop();int xt.first;int yt.second;sum;for(int i0; i4; i) {int nxxdx[i];int nyydy[i];if(nx0 || ny0) continue;if(flag[nx][ny]1 || nxm || nyn || (nx/10nx%10ny/10ny%10)k) continue;q.push({nx,ny});flag[nx][ny]1;}}return sum;
}int main() {int k,m,n;cinkmn;coutmovingCount(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/89483505https://www.cnblogs.com/wzw0625/p/12731031.html
