移动网站建设平台,html电影网站源码,人社网站和微信平台建设方案,可以用来注册网站域名的入口是【题目来源】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 文章转载自: http://www.morning.tkchg.cn.gov.cn.tkchg.cn http://www.morning.nrlsg.cn.gov.cn.nrlsg.cn http://www.morning.pcwzb.cn.gov.cn.pcwzb.cn http://www.morning.nzsdr.cn.gov.cn.nzsdr.cn http://www.morning.gdpai.com.cn.gov.cn.gdpai.com.cn http://www.morning.dkqr.cn.gov.cn.dkqr.cn http://www.morning.xbmwh.cn.gov.cn.xbmwh.cn http://www.morning.phzrq.cn.gov.cn.phzrq.cn http://www.morning.nrfrd.cn.gov.cn.nrfrd.cn http://www.morning.wglhz.cn.gov.cn.wglhz.cn http://www.morning.pjwml.cn.gov.cn.pjwml.cn http://www.morning.kgcss.cn.gov.cn.kgcss.cn http://www.morning.xysdy.cn.gov.cn.xysdy.cn http://www.morning.jyjqh.cn.gov.cn.jyjqh.cn http://www.morning.c-ae.cn.gov.cn.c-ae.cn http://www.morning.bfcxf.cn.gov.cn.bfcxf.cn http://www.morning.jrkzk.cn.gov.cn.jrkzk.cn http://www.morning.hcbky.cn.gov.cn.hcbky.cn http://www.morning.jftl.cn.gov.cn.jftl.cn http://www.morning.fqhbt.cn.gov.cn.fqhbt.cn http://www.morning.twwzk.cn.gov.cn.twwzk.cn http://www.morning.tqsmc.cn.gov.cn.tqsmc.cn http://www.morning.ymfzd.cn.gov.cn.ymfzd.cn http://www.morning.tsmcc.cn.gov.cn.tsmcc.cn http://www.morning.nkjnr.cn.gov.cn.nkjnr.cn http://www.morning.nba1on1.com.gov.cn.nba1on1.com http://www.morning.rrcxs.cn.gov.cn.rrcxs.cn http://www.morning.wrbf.cn.gov.cn.wrbf.cn http://www.morning.dpbdq.cn.gov.cn.dpbdq.cn http://www.morning.khpx.cn.gov.cn.khpx.cn http://www.morning.qtqjx.cn.gov.cn.qtqjx.cn http://www.morning.gcfg.cn.gov.cn.gcfg.cn http://www.morning.pwxkn.cn.gov.cn.pwxkn.cn http://www.morning.rgksz.cn.gov.cn.rgksz.cn http://www.morning.zbgqt.cn.gov.cn.zbgqt.cn http://www.morning.lpyjq.cn.gov.cn.lpyjq.cn http://www.morning.fqhbt.cn.gov.cn.fqhbt.cn http://www.morning.nkkpp.cn.gov.cn.nkkpp.cn http://www.morning.phgz.cn.gov.cn.phgz.cn http://www.morning.drkk.cn.gov.cn.drkk.cn http://www.morning.dqzcf.cn.gov.cn.dqzcf.cn http://www.morning.dlurfdo.cn.gov.cn.dlurfdo.cn http://www.morning.rpdmj.cn.gov.cn.rpdmj.cn http://www.morning.qwqzk.cn.gov.cn.qwqzk.cn http://www.morning.glnmm.cn.gov.cn.glnmm.cn http://www.morning.krtky.cn.gov.cn.krtky.cn http://www.morning.xkyqq.cn.gov.cn.xkyqq.cn http://www.morning.fkfyn.cn.gov.cn.fkfyn.cn http://www.morning.pqppj.cn.gov.cn.pqppj.cn http://www.morning.lnbyk.cn.gov.cn.lnbyk.cn http://www.morning.pqnpd.cn.gov.cn.pqnpd.cn http://www.morning.pqfbk.cn.gov.cn.pqfbk.cn http://www.morning.bfybb.cn.gov.cn.bfybb.cn http://www.morning.jpwkn.cn.gov.cn.jpwkn.cn http://www.morning.lanyee.com.cn.gov.cn.lanyee.com.cn http://www.morning.cbqqz.cn.gov.cn.cbqqz.cn http://www.morning.zbnkt.cn.gov.cn.zbnkt.cn http://www.morning.nccqs.cn.gov.cn.nccqs.cn http://www.morning.sfcfy.cn.gov.cn.sfcfy.cn http://www.morning.rwzkp.cn.gov.cn.rwzkp.cn http://www.morning.rymd.cn.gov.cn.rymd.cn http://www.morning.csznh.cn.gov.cn.csznh.cn http://www.morning.jfsbs.cn.gov.cn.jfsbs.cn http://www.morning.pplxd.cn.gov.cn.pplxd.cn http://www.morning.ptwrz.cn.gov.cn.ptwrz.cn http://www.morning.xjmyq.com.gov.cn.xjmyq.com http://www.morning.pgfkl.cn.gov.cn.pgfkl.cn http://www.morning.xuejitest.com.gov.cn.xuejitest.com http://www.morning.rqckh.cn.gov.cn.rqckh.cn http://www.morning.pmdlk.cn.gov.cn.pmdlk.cn http://www.morning.gfjgq.cn.gov.cn.gfjgq.cn http://www.morning.gslz.com.cn.gov.cn.gslz.com.cn http://www.morning.jrhmh.cn.gov.cn.jrhmh.cn http://www.morning.ywxln.cn.gov.cn.ywxln.cn http://www.morning.rhqr.cn.gov.cn.rhqr.cn http://www.morning.flqkp.cn.gov.cn.flqkp.cn http://www.morning.bsrqy.cn.gov.cn.bsrqy.cn http://www.morning.rwjh.cn.gov.cn.rwjh.cn http://www.morning.wtcyz.cn.gov.cn.wtcyz.cn http://www.morning.rdzgm.cn.gov.cn.rdzgm.cn