洛谷 P1747 好奇怪的游戏 C语言 bfs

题目：

https://www.luogu.com.cn/problem/P1747#submit

题目描述

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

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

输入格式

第一行两个整数 x1,y1。

第二行两个整数 x2,y2

输出格式

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

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

思路：简单的两次bfs，用函数就好了，不过记得要用memset重置下状态数组stl。

代码如下：

#include <iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int dx[12]={2,2,-2,-2,-1,-1,1,1,-2,-2,2,2};
int dy[12]={2,-2,2,-2,-2,2,-2,2,1,-1,1,-1};
struct Node{
	int x;
	int y;
	int step;
};
int map[100][100];
bool stl[100][100];
int x1,y1,x2,y2;
int bfs(int x,int y)
{
	queue <Node> q;
	Node start = {x,y,0};
	q.push(start);
	stl[x][y] = true;//标记已走过 
	while(!q.empty())
	{
		int x = q.front().x;//取出队首的三个数据 
		int y = q.front().y;
		int step = q.front().step;
		if(x == 1 && y ==1)
		{
		   return step ;
			break;
		}
		for(int k = 0 ; k < 12 ; k++)
		{
			int tx = x + dx[k];
			int ty = y + dy[k];
			if(stl[tx][ty] == false && tx >=1 && tx <= 20 && ty >=1 && ty <= 20 )
			{
				stl[tx][ty] = true;//标记已访问 
				Node newpos ={tx,ty,step+1};
				q.push(newpos);
			}
		 } 
		 q.pop();
	}
	return -1;
}
int main() 
{
	cin >> x1 >> y1 >> x2 >> y2;
	
 	cout << bfs(x1,y1) << endl;
 	memset(stl,false,sizeof stl);
	cout << bfs(x2,y2) << endl;

	return 0;
}