https://www.luogu.com.cn/problem/P1443
題目描述
有一個n*m的棋盤(1<n,m<=400)，在某個點上有一個馬,要求你計算出馬到達棋盤上任意一個點最少要走幾步
輸入格式
一行四個資料，棋盤的大小和馬的坐標
輸出格式
一個n*m的矩陣，代表馬到達某個點最少要走幾步（左對齊，寬5格，不能到達則輸出-1）
輸入輸出樣例
輸入 #1復制
3 3 1 1
輸出 #1復制
0 3 2 3 -1 1 2 1 4
題解：一般情況下的BFS，每個能走的方向都保存下來，更新需要輸出的地圖，BFS的寫法就是一般的寫法，注意的是輸出時需要寬5格，一開始用了cin，不太熟練使用格式化輸出，就改成了scanf/printf輸入輸出了，
#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mp[410][410];
int vis[410][410];
struct node
{
int x,y,step;
} w,l;
int dx[] = {-1,-1,-2,-2,1,1,2,2};
int dy[] = {-2,2,-1,1,-2,2,1,-1};
void bfs(int sx, int sy,int n, int m)
{
memset(vis,0,sizeof(vis));
memset(mp,-1,sizeof(mp));
queue<node>q;
w.x = sx;
w.y = sy;
w.step = 0;
q.push(w);
vis[w.x][w.y] = 1;
mp[sx][sy] = 0;
while(!q.empty())
{
w = q.front();
q.pop();
for(int i = 0; i < 8; i ++)
{
int tx = dx[i] + w.x;
int ty = dy[i] + w.y;
if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && vis[tx][ty] == 0)
{
l.x = tx;
l.y = ty;
l.step = w.step+1;
q.push(l);
vis[tx][ty] = 1;
mp[tx][ty] = l.step;
}
}
}
}
int main()
{
int n,m,sx,sy;
// cin >> n >> m >> sx >> sy;
scanf("%d %d %d %d", &n,&m,&sx,&sy);
bfs(sx,sy,n,m);
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
// if(j == 1)
// cout << mp[i][j];
// else
// cout << " " << mp[i][j] ;
printf("%-5d",mp[i][j]);
}
printf("\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/153282.html
標籤：其他
下一篇：PA1