洛谷1443—-马的遍历

1001-高同学

发表文章数:265

热门标签

首页 » LeetCode » 正文

这道题题目意思没有表达明确。我以为是每个坐标都要进行搜索,其实不是,就是很正常的一次bfs就可以

题目链接:https://www.luogu.com.cn/problem/P1443

#include <bits/stdc++.h>
#define MAXN 450
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int dir[8][2]={{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
int mp[MAXN][MAXN];
int vis[MAXN][MAXN];
int n,m;
struct node
{
	int x;
	int y;
	int step;
	node()
	{
		x=0;y=0;
		step=0;
	}
};

void bfs(int x,int y)
{
	
	node p,q;
	p.step=0;
	p.x=x;
	p.y=y;
	queue<node> que;
	que.push(p);
	
	while(!que.empty())
	{
		q=que.front();
		que.pop();
	
		int dx=q.x,dy=q.y,s=q.step;
		for(int i=0; i<8; i++)
		{
			int xx=dx+dir[i][0];
			int yy=dy+dir[i][1];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy])
			{
				vis[xx][yy]=1;
				p.x=xx;
				p.y=yy;
				p.step=s+1;
				mp[xx][yy]=p.step;
				que.push(p);
			}
		}
	}
	while(!que.empty())
	{
		que.pop();
	}
	return ;
}

int main(int argc, char** argv)
{
	cin>>n>>m;
	int x,y;
	cin>>x>>y;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			
			mp[i][j]=-1;
			
		}
	}
	vis[x][y]=1;
	mp[x][y]=0;
	bfs(x,y);
	for(int i=1; i<=n; i++)
	{
		
		for(int j=1; j<=m; j++)
		{
			printf("%-5d",mp[i][j]);
		}
		cout<<endl;
	}
	return 0;
}

 

标签:

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《洛谷1443—-马的遍历》 发布于2020-03-09

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录