洛谷 P1747 好奇怪的游戏

题目背景

《爱与愁的故事第三弹·shopping》娱乐章。

调调口味来道水题。

题目描述

爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点 �1,�1x1​,y1​ 和 �2,�2x2​,y2​ 上。它们得从点 �1,�1x1​,y1​ 和 �2,�2x2​,y2​ 走到 (1,1)(1,1)。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到 (1,1)(1,1) 的最少步数，你能帮他解决这个问题么？

注意不能走到 �x 或 �y 坐标 ≤0≤0 的位置。

输入格式

第一行两个整数 �1,�1x1​,y1​。

第二行两个整数 �2,�2x2​,y2​。

输出格式

第一行一个整数，表示黑马到 (1,1)(1,1) 的步数。

第二行一个整数，表示白马到 (1,1)(1,1) 的步数。

输入输出样例

输入 #1复制

12 16
18 10

输出 #1复制

8 
9

说明/提示

数据范围及约定

对于 100%100% 数据，1≤�1,�1,�2,�2≤201≤x1​,y1​,x2​,y2​≤20。

分析：

        对于该题，我们选择bfs，难点主要有三个，一个是如何走 日 如何走田  一个是怎么去表示走的步数，另一个就是对于二维数组我们怎么去存到队列里。

        对于第一个问题呢，我们还是用最简单的数组方法去实现走日和走田。定义xrr yrr分别存储x和y方向，拿走日为例，如果马向右上走，那是不是x需要加一，同时y需要加一，如果往右下走呢，是不是x需要加一，y需要减一...那么一共有多少种情况呢？如果把走田也算上的话一共有12种情况：走日：右上，右下，左上...走田：右上，右下，左上，左下。那我们就可定义xrr[12]，yrr[12]，分别储存右上，右下..等12种情况，到时候加一个循环是不是就可以实现了。

        对于第二个问题，如何表示步数，我们可以把地图用二维数组map表示，map的值初始化为-1，每到一个点我们就把他赋值为队列第一个点的数值加一。（这里因用的是bfs，和queue结合使用，如果不是很了解bfs的同学建议先去学习bfs的原理）

        对于第三个问题，如何把一个点存到队列里，我比较菜，没想到更好地方法，我就开了两个队列，分别存储点的x和y值，这样两个队列一结合就是求得map里的点。

        OK，那么bfs部就没什么好说的，还是那些固定模板，上代码！

代码：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int xrr[12] = { 1,1,-1,-1,2,2,-2,-2, 2,2,-2,-2 };//日：右上 右下 左上 左下 右右上 右右下 左左上 左左下 田：右上 右下 左上 左下
int yrr[12] = { 2,-2,2,-2,1,-1,1,-1, -2,2,-2,2 };
int bx, by, wx, wy;
int map[62][62];
queue<int>q_x;//放一个点的x数值
queue<int>q_y;//放一个点的y数值

void bfs(int x, int y)
{
	bool sign = false;//用来记录是否找到了1,1
	while (q_x.size())
	{
		for (int i = 0; i < 12; i++)
		{
			int tx, ty;
			tx = q_x.front() + xrr[i];
			ty = q_y.front() + yrr[i];
			if (tx < 1 || ty < 1)
				continue;
			if (map[tx][ty] != -1)
				continue;
			q_x.push(tx);
			q_y.push(ty);
			map[tx][ty] = map[q_x.front()][q_y.front()] + 1;//用map数值来表示多少步
			if (tx == 1 && ty == 1)
			{
				cout << map[tx][ty] << endl;
				sign = true;
				break;
			}
		}
		if (sign == true)
			break;
		q_x.pop();
		q_y.pop();
	}
}

int main()
{
	cin >> bx >> by >> wx >> wy;
	//黑马
	memset(map, -1, sizeof(map));//把map全部重置成-1
	map[bx][by] = 0;//把起点记为0，表示不需要操作就能到
	q_x.push(bx);//x入队
	q_y.push(by);//y入队
	bfs(bx, by);

	//清空队列和地图
	queue<int>empty1;
	queue<int>empty2;
	swap(q_x, empty1);//清空栈
	swap(q_y, empty2);//清空栈
	//白马
	memset(map, -1, sizeof(map));
	map[wx][wy] = 0;
	q_x.push(wx);
	q_y.push(wy);
	bfs(wx, wy);
	return 0;
}