洛谷P1443 马的遍历（bfs，注意输出格式）

题目描述

有一个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，输出的时候比较坑是%-5d

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<stack>

#include<vector>

#include<set>

#include<map>

#include<cmath>

#include<list>

#define N 300005 

typedef long long ll;

using namespace std;

int Map[405][405];

int vis[405][405];

int n,m,sx,sy;

struct node

{

	int x, y;

	int step;

};

int dir[8][2]={{2,1},{1,2},{2,-1},{1,-2},{-2,1},{-1,2},{-1,-2},{-2,-1}};

void bfs(int x,int y)

{

	queue<node>q;

	node start;

	start.x=x;

	start.y=y;

	start.step=0;

	Map[x][y]=start.step;

	q.push(start);

	while(!q.empty())

	{

		node now=q.front();

		q.pop();

		for(int t=0;t<8;t++)

		{

			node next;

			next.x=now.x+dir[t][0];

			next.y=now.y+dir[t][1];

			next.step=now.step+1;

			if(next.x>=1&&next.x<=n&&next.y>=1&&next.y<=m&&vis[next.x][next.y]==0)

		   {

		   	q.push(next);

		   	vis[next.x][next.y]=1;

		   	Map[next.x][next.y]=next.step;

			}

		}

	}

}

int main()

{

	cin>>n>>m>>sx>>sy;

	vis[sx][sy]=1;

	memset(Map,-1,sizeof(Map));

    bfs(sx,sy);

    for(int t=1;t<=n;t++)

    {

    	for(int j=1;j<=m;j++)

    	{

    		printf("%-5d",Map[t][j]);

		}

		cout<<endl;

	}

	return 0;

}

巴特西

洛谷P1443 马的遍历（bfs，注意输出格式）

题目描述

输入输出格式

输入输出样例

最新文章

热门文章