洛谷:P1443马的遍历-创新互联

题目描述

有一个 n×m 的棋盘,在某个点 (x, y)上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。

创新互联的客户来自各行各业,为了共同目标,我们在工作上密切配合,从创业型小企业到企事业单位,感谢他们对我们的要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。专业领域包括网站建设、成都网站设计、电商网站开发、微信营销、系统平台开发。输入格式

输入只有一行四个整数,分别为 n, m, x, y。

输出格式

一个 n×m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 −1)。

输入输出样例

输入 #1复制

3 3 1 1

输出 #1复制

0    3    2    
3    -1   1    
2    1    4   
说明/提示 数据规模与约定

对于全部的测试点,保证 1≤x≤n≤400,1≤y≤m≤400。

题解:

基础的bfs搜索,练手用,由于stl还不熟练,所以这一题的容器没有用queue,思路个人感觉蛮清  晰了。

不啰嗦了,可以看下注释哦。

AC代码:

#include#define ll long long
using namespace std;
struct que{
	int x,y,s;
}q[160100];//得开够,400*400以上 

int main()
{
	int n,m,i,j,sx,sy,nextx,nexty;
	cin>>n>>m>>sx>>sy;
	
	int head=1,tail=1,k,a[405][405],direct[8][2]{ 
		{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}  
	};//定义方向数组 
	memset(a,-1,sizeof(a));//初始化数组为-1 
	
	q[head].x=sx;
	q[head].y=sy;
	q[head].s=0;
	tail++;
	a[sx][sy]=0;
	while(headn||nexty>m||nextx<1||nexty<1)continue;//试探边界限制 
		
		if(a[nextx][nexty]==-1)
		{
			q[tail].x=nextx;
			q[tail].y=nexty;
			q[tail].s=q[head].s+1;//父亲的步数 加 1 
			a[nextx][nexty]=q[tail].s;
			tail++;//尾指针 加 1 
	    }
	  }
	  head++;//头指针 加 1 ! 
	}
	
	for(i=1;i<=n;i++)//输出 
	{
		for(j=1;j<=m;j++)
		{
			cout<

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章标题:洛谷:P1443马的遍历-创新互联
链接分享:http://scyanting.com/article/dpdojj.html