P1443 馬的遍歷

# P1443 馬的遍歷

## 題目描述

有一個 $n \times m$ 的棋盤，在某個點 $(x, y)$ 上有一個馬，要求你計算出馬到達棋盤上任意一個點最少要走幾步。

## 輸入格式

輸入只有一行四個整數，分別為 $n, m, x, y$。

## 輸出格式

一個 $n \times m$ 的矩陣，代表馬到達某個點最少要走幾步（不能到達則輸出 $-1$）。

## 輸入輸出樣例 #1

### 輸入 #1

```
3 3 1 1
```

### 輸出 #1

```
0 ? ?3 ? ?2 ? ?
3 ? ?-1 ? 1 ? ?
2 ? ?1 ? ?4
```

## 說明/提示

### 數據規模與約定

對于全部的測試點，保證 $1 \leq x \leq n \leq 400$，$1 \leq y \leq m \leq 400$。

題目描述?有一個n*m的棋盤(1<n,m<=400)，在某個點上有一個馬,要求你計算出馬到達棋盤上任意一個點最少要走幾步?輸入格式?一行四個數據，棋盤的大小和馬的坐標?輸出格式?一個n乘m的矩陣，代表馬到達某個點最少要走幾步（左對齊，寬5格，不能到達則輸出-1）?輸入輸出樣例?輸入?3 3 1 1?輸出?0 3 2
3 -1 1
2 1 4
分析?這道題我們可以用深搜（BFS） 很簡單，不會BFS的可以參考?騎士旅行（BFS）?AC代碼

#include<iostream>
#include<cstdio>
int n,m,x1,y1,head,tail,a[405][405],b[405][405],st[160005][3];
int dx[9]={0,1,1,-1,-1,2,2,-2,-2};//八個方向
int dy[9]={0,2,-2,2,-2,1,-1,1,-1};
void bfs()
{while(head<tail)//BFS模板{head++;for(int i=1;i<=8;i++)//八個方向{int x=st[head][0]+dx[i],y=st[head][1]+dy[i];if(x>=1&&x<=n&&y>=1&&y<=m)//是否出界if(a[x][y]==0)//是否被標記過{tail++;a[x][y]=1;//標記b[x][y]=st[tail][2]=st[head][2]+1;//賦值st[tail][0]=x;//更新坐標st[tail][1]=y;}}}
}
using namespace std;
int main()
{cin>>n>>m;cin>>x1>>y1;a[x1][y1]=1;//標記st[1][0]=x1;st[1][1]=y1;//坐標tail=1;//初值bfs();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)if(a[i][j]!=0)printf("%-5d",b[i][j]);//輸出需要else printf("%-5d",-1);cout<<endl;}
}