洛谷-馬的遍歷
來源：https://www.luogu.com.cn/problem/P1443
題目描述
有一個n*m的棋盤(1<n,m<=400)，在某個點上有一個馬,要求你計算出馬到達棋盤上任意一個點最少要走幾步
輸入格式
一行四個資料，棋盤的大小和馬的坐標
輸出格式
一個n*m的矩陣，代表馬到達某個點最少要走幾步（左對齊，寬5格，不能到達則輸出-1）
樣例
輸入
3 3 1 1
**輸出 **
0 3 2
3 -1 1
2 1 4
看到題目第一想法是~
1：馬是怎么走的？哈哈哈哈哈，，，
“馬”走動的方法是每步一直一斜，即先橫著或直著走一格，然后再斜著走一個對角線，俗稱“馬走日”，在“日”的對角線上兩點可以一步到達，其他地方不能到達，如圖所示，
| （x-2,y-1） | （x-2,y+1） | |||
|---|---|---|---|---|
| （x-1,y-2） | （x-1,y+2） | |||
| (x,y)馬 | ||||
| （x+1,y-2） | （x+1,y+2） | |||
| （x+2,y-1） | （x+2,y+1） |
2：左對齊，寬5格咋搞，百度即得 printf("%-5d",a);
3：然后想到了廣度優先搜索，讓我們先來解釋一下這種搜索方式，
例如：這棵樹
BFS搜索，假設從1開始，然后遍歷和1相鄰的2,3,4，接著通過2,3,4遍歷5 6 7 8 9 10（注意順序）
實作程序是通過一個佇列：（這里通過陣串列示的佇列）
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
當頭指標等于尾指標時，遍歷完畢，或者說符合條件的點，已經遍歷完畢，
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
我們可以發現每一次的遍歷都離原始點1是相同的距離，所以當我們做某些最短路徑的題時候，可以考慮一下bfs，
先來一個模板：
BFS模板（廣度優先搜索）
void bfs()
{
初始化，初始狀態存陣列;
int head=0,tail=1，que[max_size];//構建佇列
標記初始點
while(head<tail)
{
head++;//指向待擴展結點
for(i=1;i<=maxi;++i)
{
if(滿足條件||不重復)
{
tail++;
將新節點存入佇列
}
}
}
}
具體操作：
1：選擇一個二維陣列res[] [],先全部賦值為-1，里面存放到最終結果（棋盤上每一點的最短步數）
2： 用一個結構體陣列a來表示馬所在的位置，并充當BFS模板的佇列，head,tail,充當佇列的頭尾指標
3：兩個陣列x[],y[]聯合表示馬可以到達的八個位置，用于判斷是否符合條件，然后就是要注意在判斷的時候不要越界就好啦，
然后是不是感覺來了，那就自己先試一試吧，萬一就AC了呢，
完整代碼：
#include<bits/stdc++.h>
int n,m,nx,ny;
int res[405][405];//res表示最終輸出結果，下標代表棋盤位置，值代表最少步數
int x[8]={1,2,-1,-2,-1,-2,1,2};
int y[8]={2,1,2,1,-2,-1,-2,-1};
struct queue{
int x,y;
}a[40010];//構建bfs的佇列（用陣串列示）
void bfs(int i,int j)
{
int head=1,tail=2;
a[2].x=i,a[2].y=j;
res[i][j]=0;//初始位置的最少步數為0
while(head<tail)
{
head++;
for(int q=0;q<8;q++)
{
//(xx,yy)表示目前馬走到的位置，還有，，，~~變數名真的好難取~~
int xx=a[head].x+x[q];
int yy=a[head].y+y[q];
if((res[xx][yy]==-1) && xx>=1 && xx<=n && yy>=1 && yy<=m)//判斷是否走過，是否越界
{
tail++;
res[xx][yy]=res[a[head].x][a[head].y]+1;//最少步數加一
a[tail].x=xx;
a[tail].y=yy;
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&nx,&ny);
memset(res,-1,sizeof res);
bfs(nx,ny);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%-5d",res[i][j]);
}
printf("\n");
}
}
歡迎大家友好評論呀，有啥問題dd我呀，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/190503.html
標籤：其他