洛谷题解 P1443 【马的遍历】 发表于 2019-05-13 | 更新于 2020-03-26 | 阅读次数: 本文字数: 1.5k | 阅读时长 ≈ 1 分钟 主要思想 bfs运用队列queue减少代码量(坐标数组)简单点来说就是先从马的位置开始搜索,搜索马可以到达的点: 蓝色点即为马可以到达的点(马走日),红色为马所在位置: 上代码: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include<iostream>#include<cstdio>#include<queue>#include<cstring>using namespace std;int node[9][2]={{0,0},{-2,1},{1,-2},{2,-1},{-1,2},{2,1},{-2,-1},{1,2},{-1,-2}};//坐标数组,节省代码量int n,m,xs,ys,map[401][401];struct zb//结构体{ int x,y,bu;};queue<zb> Q;//队列int main(){ cin>>n>>m>>xs>>ys;//输入 memset(map,10000,sizeof(map));//初始化,便于后面的搜索比较和输出 map[xs][ys]=0;//一定要是0(马所在点步数为0) Q.push((zb){xs,ys,0});//进队 while(!Q.empty()) { zb news=Q.front(); Q.pop(); for(int a=1;a<=8;a++) { if(news.y+node[a][1]>0&&news.y+node[a][1]<=m&&news.x+node[a][0]>0&&news.x+node[a][0]<=n&&map[news.x+node[a][0]][news.y+node[a][1]]>news.bu+1)//又长又臭的if语句,比较步数,判断是否越界 { map[news.x+node[a][0]][news.y+node[a][1]]=news.bu+1;//更新 Q.push((zb){news.x+node[a][0],news.y+node[a][1],news.bu+1}); } } } for(int a=1;a<=n;a++) { for(int b=1;b<=m;b++) { if(map[a][b]>=10000) { printf("%-5d",-1); } else { printf("%-5d",map[a][b]); } } cout<<endl; }} 就这么简单,预祝明日特长生考试通过!题目详见:https://www.luogu.org/problemnew/show/P1443