欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P1443 马的遍历 (BFS)

程序员文章站 2022-06-11 20:37:19
...

题目描述

P1443 马的遍历 (BFS)

代码

#include<bits/stdc++.h> 
typedef long long ll;
using namespace std;
const int maxn = 500;
int n,m,sx,sy,vis[maxn][maxn],ans[maxn][maxn];
int fx[16]={2,-2,2,-2,-1,1,-1,1},fy[16]={1,1,-1,-1,2,2,-2,-2};//方向
void bfs(){
	queue<pair<int,int> >q;
	//初始节点的初始化 
	q.push(make_pair(sx,sy));
	vis[sx][sy] = 1;
	ans[sx][sy] = 0;
	while(!q.empty()){
		//取出队首节点 
		int xx = q.front().first,yy = q.front().second;
		q.pop();
		for(int i = 0;i< 8;i++){
			//循环每个方向 
			int dx = xx + fx[i];
			int dy = yy + fy[i];
			if(dx <1 || dx > n || dy < 1|| dy > m || vis[dx][dy] == 1)
				continue;
			vis[dx][dy] = 1;
			q.push(make_pair(dx,dy));
			ans[dx][dy] = ans[xx][yy] + 1;
		}
	}
}
int main(){
	//freopen("a.txt","r",stdin); 
	memset(ans,-1,sizeof ans);
	cin>>n>>m>>sx>>sy;
	bfs();
	for(int i =1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			printf("%-5d",ans[i][j]);
		}
		cout<<endl;
	}
	return 0;
} 

要点:

make_pair() :pair的初始化
printf 默认右对齐:printf("%5d",a) ,左对齐加负号:printf("%-5d",a);

相关标签: c++算法