【C++ 真题】P1747 好奇怪的游戏
P1747 好奇怪的游戏
题目背景
《爱与愁的故事第三弹·shopping》娱乐章。
调调口味来道水题。
题目描述
爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点 x 1 , y 1 x_1,y_1 x1,y1 和 x 2 , y 2 x_2,y_2 x2,y2 上。它们得从点 x 1 , y 1 x_1,y_1 x1,y1 和 x 2 , y 2 x_2,y_2 x2,y2 走到 ( 1 , 1 ) (1,1) (1,1)。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到 ( 1 , 1 ) (1,1) (1,1) 的最少步数，你能帮他解决这个问题么？
注意不能走到 x x x 或 y y y 坐标 ≤ 0 \le 0 ≤0 的位置。
输入格式
第一行两个整数 x 1 , y 1 x_1,y_1 x1,y1。
第二行两个整数 x 2 , y 2 x_2,y_2 x2,y2。
输出格式
第一行一个整数，表示黑马到 ( 1 , 1 ) (1,1) (1,1) 的步数。
第二行一个整数，表示白马到 ( 1 , 1 ) (1,1) (1,1) 的步数。
输入输出样例 #1
输入 #1
12 16
18 10
输出 #1
8
9
说明/提示
数据范围及约定
对于 100 % 100\% 100% 数据， 1 ≤ x 1 , y 1 , x 2 , y 2 ≤ 20 1\le x_1,y_1,x_2,y_2 \le 20 1≤x1,y1,x2,y2≤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;
}