题目背景 《爱与愁的故事第三弹·shopping》娱乐章。
调调口味来道水题。
题目描述 爱与愁大神坐在公交车上无聊，于是玩起了手机。
一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。
这个游戏类似象棋，但是只有黑白马各一匹，在点 (x1, y1) 和 (x2, y2) 上，它们得从点 (x1, y1) 和 (x2, y2) 走到 (1, 1)。
这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。
现在爱与愁大神想知道两匹马到 (1, 1) 的最少步数，你能帮他解决这个问题么？
输入格式 第 1 行：两个整数 x1，y1 第 2 行：两个整数 x2，y2
输出格式 第 1 行：黑马到 (1, 1) 的步数 第 2 行：白马到 (1, 1) 的步数
输入样例 12 16 18 10
输出样例 8 9
数据范围 对于 100% 数据：x1, y1, x2, y2 ≤ 20
题解 BFS：
#include <iostream> #include <cstring> #include <cstdio> #include <queue> #define x first #define y second using namespace std; typedef pair<int, int > PII; const int N = 25; int x, y; int dist[N][N]; int dx[12] = {1, 1, -1, -1, 2, 2, -2, -2, -2, -2, 2, 2}; int dy[12] = {2, -2, 2, -2, 1, -1, 1, -1, -2, 2, -2, 2}; int bfs(int x, int y) { queue<PII> q; q.push(make_pair(1, 1)); dist[1][1] = 0; while(q.size()) { PII t = q.front(); q.pop(); if(t.x == x && t.y == y) return dist[x][y]; for (int i = 0; i < 12; i ++) { int a = t.x + dx[i], b = t.y + dy[i]; if(a < 1 || a > 20 || b < 1 || b > 20 || dist[a][b] != -1) continue; q.push(make_pair(a, b)); dist[a][b] = dist[t.x][t.y] + 1; } } } int main() { cin >> x >> y; memset(dist, -1, sizeof dist); cout << bfs(x, y) << endl; cin >> x >> y; memset(dist, -1, sizeof dist); cout << bfs(x, y) << endl; return 0; }