洛谷：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://6mz.cn/article/dpdojj.html