【C++ 真题】P1747 好奇怪的游戏

P1747 好奇怪的游戏

题目背景

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

调调口味来道水题。

题目描述

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

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

输入格式

第一行两个整数 $x_1,y_1$。

第二行两个整数 $x_2,y_2$。

输出格式

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

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

输入输出样例 #1

输入 #1

12 16
18 10

输出 #1

8 
9

说明/提示

数据范围及约定

对于 $100\%$ 数据，$1\le x_1,y_1,x_2,y_2\le 20$。

题解

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7;

int x11, y11, x22, y22, m, n, st = 0;
bool vis[N][N]; 
int rx[] = {0, -2, -2, -1, 1, 2, 2, 2, 2, 1, -1, -2, -2};
int ry[] = {0, -1, -2, -2, -2, -2, -1, 1, 2, 2, 2, 2, 1};//顺时针 

struct pl{
	int x, y, s;
};

queue<pl> pass;

int bfs(int x, int y){
	if(x == 1 && y == 1) return 0;
	vis[x][y] = 1;
	while(!pass.empty()){
		pl pass1 = pass.front();
		pass.pop();
 
		for(int i=1;i<=12;++i){
			int nx = rx[i] + pass1.x;
			int ny = ry[i] + pass1.y;
			if(nx<=0 || nx>n || ny<=0 || ny>m || vis[nx][ny]) continue;
			if(nx == 1 && ny == 1) return pass1.s+1;
			vis[nx][ny] = 1;	
			pass.push({nx, ny, pass1.s+1}); 
		}
	}
	return 0;
}

int main(){
	cin>>x11>>y11>>x22>>y22;
	n = max(x11, x22)+1;
	m = max(y11, y22)+1;
	memset(vis, 0, sizeof(vis));
	while(!pass.empty()) pass.pop();
	pass.push({x11, y11, 0});
	cout<<bfs(x11, y11)<<endl;
	
	memset(vis, 0, sizeof(vis));
	while(!pass.empty()) pass.pop();
	pass.push({x22, y22, 0});
	cout<<bfs(x22, y22)<<endl;
	
	return 0;
}