题目描述
有一个 n×m 的棋盘,在某个点 (x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数,分别为 n,m,x,y。
输出格式
一个 n×m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 −1)。
输入输出样例
输入 #13 3 1 1输出 #1
0 3 2 3 -1 1 2 1 4
题目很简单,但是这里要注意啊,他说的最短路径,为了避免麻烦还是直接宽搜的好
我发出来主要是我发现了个很有意思的事情,先看一下我mle和tle的代码:
#include<bits/stdc++.h> using namespace std; const int N=500; int n,m,a,b,mp[N][N]; int dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={2,1,-1,-2,2,1,-1,-2}; struct node{ int x,y,step; }; int vis[N][N]; void bfs() { queue<node>que; node str; str.x=a,str.y=b,str.step=0; que.push(str); vis[a][b]=0; while(!que.empty()){ node now=que.front(); que.pop(); vis[now.x][now.y]=now.step; for(int i=0;i<8;i++){ int x1=now.x+dx[i],y1=now.y+dy[i]; if(x1>=1&&y1>=1&&x1<=n&&y1<=m&&vis[x1][y1]==-1){ node next; next.x=x1,next.y=y1,next.step=now.step+1; que.push(next); } } } return ; } int main() { cin>>n>>m>>a>>b; memset(vis, -1, sizeof vis); bfs(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cout<<vis[i][j]<<" "; cout<<endl; } return 0; }
接着是ac的代码:
#include<bits/stdc++.h> using namespace std; const int N=500; int n,m,a,b,mp[N][N]; int dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={2,1,-1,-2,2,1,-1,-2}; struct node{ int x,y,step; }; int vis[N][N]; void bfs() { queue<node>que; node str; str.x=a,str.y=b,str.step=0; que.push(str); vis[a][b]=0; while(!que.empty()){ node now=que.front(); que.pop(); for(int i=0;i<8;i++){ int x1=now.x+dx[i],y1=now.y+dy[i]; if(x1>=1&&y1>=1&&x1<=n&&y1<=m&&vis[x1][y1]==-1){ node next; next.x=x1,next.y=y1,next.step=now.step+1; vis[x1][y1]=now.step+1; que.push(next); } } } return ; } int main() { cin>>n>>m>>a>>b; memset(vis, -1, sizeof vis); bfs(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cout<<vis[i][j]<<" "; cout<<endl; } return 0; }
我在这里主要想讨论在for循环里面,为什么如果不先标记vis数组就会爆t爆m
因为我在外层循环是有标记的,然后呢我想了下,确实不行,因为我们这是宽搜,搜过的不能再搜了
如果不立马标记的话,会发生另外一队来搜的时候,发现你这个点还是没标记,然后再给你标记一下,这样就导致不对了
所以会增加时间和空间,就会爆掉
标签:node,遍历,int,bfs,vis,更深一层,que,str From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17473174.html