https://www.luogu.com.cn/problem/P1443

#include<cstdio>
#include<queue>
using namespace std;
struct locate
{
? ?int x;//橫坐標
? ?int y;//縱坐標
};
int direction[8][2]={
? ? ? ?{-1,-2},
? ? ? ?{+1,-2},
? ? ? ?{-2,-1},
? ? ? ?{+2,-1},
? ? ? ?{-2,+1},
? ? ? ?{+2,+1},
? ? ? ?{-1,+2},
? ? ? ?{+1,+2}
};
int main()
{
? ?int n, m, a, b;//n代表矩陣行數(shù)m代表矩陣列數(shù)x和y是起始坐標
? ?scanf("%d %d %d %d", &n, &m, &a, &b);
? ?locate first;//第一個起點
? ?first.x = a;
? ?first.y = b;
? ?int result[401][401] ;//用于存儲最小值結果沒有訪問過則用-1代表，那么此時就不可以用訪問過的全部點數(shù)去判斷循環(huán)是否會終止
? ?for(int i=1;i<=n;i++)
? ? ? ?for(int j=1;j<=m;j++)
? ? ? ?{
? ? ? ? ? ?result[i][j]=-1;
? ? ? ?}
? ?//定義BFS隊列
? ?queue<locate> Q;
? ?Q.push(first);
? ?bool visited[401][401];//用于確定此點是否被訪問過
? ?//初始化所有點未被訪問
? ?for(int i=1;i<=n;i++)
? ? ? ?for(int j=1;j<=m;j++)
? ? ? ?{
? ? ? ? ? ?visited[i][j]=false;
? ? ? ?}
? ?visited[first.x][first.y]=true;//起始坐標標記為訪問過
? ?result[first.x][first.y]=0;//起始點到自身的距離為0
? ?//需定義距離dist，每次出隊并把相鄰節(jié)點加入時則距離加一
? ?while (Q.empty()==false)//在隊列為空是循環(huán)停止說明已經訪問玩圖中的全部元素
? ?{
? ? ? ?//隊頭元素出隊用head保存隊頭元素
? ? ? ?locate head=Q.front();
? ? ? ?Q.pop();//出隊
? ? ? ?//每次的result結果應該是出隊元素的result的基礎上增加一
? ? ? ?//還沒有遍歷結束則遍歷所有的鄰居
? ? ? ?//要判斷此時的鄰居有沒有超過矩陣的邊界
? ? ? ?for(int i=0;i<8;i++)
? ? ? ?{
? ? ? ? ? ?//定義臨時變量用于保存此時周圍的八個點的臨時信息
? ? ? ? ? ?locate temp;
? ? ? ? ? ?temp.x=head.x+direction[i][0];
? ? ? ? ? ?temp.y=head.y+direction[i][1];
? ? ? ? ? ?if(head.x+direction[i][0]>=1&&head.x+direction[i][0]<=n&&
? ? ? ? ? ? ? head.y+direction[i][1]>=1&&head.y+direction[i][1]<=m&&
? ? ? ? ? ? ? visited[head.x+direction[i][0]][head.y+direction[i][1]]==false)//沒有超過行的范圍也沒有超過列的范圍并且此點也沒有訪問過
? ? ? ? ? ?{
? ? ? ? ? ? ? ?Q.push(temp);
? ? ? ? ? ? ? ?visited[temp.x][temp.y]=true;//標記為訪問過
? ? ? ? ? ? ? ?//給每個鄰接點賦予此時的距離值
? ? ? ? ? ? ? ?result[temp.x][temp.y]=result[head.x][head.y]+1;//從出隊元素的距離基礎上加一
? ? ? ? ? ?}
? ? ? ?}
? ?}
? ?//遍歷結束則打印result矩陣
? ?for(int i=1;i<=n;i++)
? ?{
? ? ? ?for (int j = 1; j <= m; j++)
? ? ? ? ? ?printf("%d ", result[i][j]);
? ? ? ?printf("\n");
? ?}
}
//