文章目录
一、P1747 好奇怪的游戏
总结
一、P1747 好奇怪的游戏
本题链接：P1747 好奇怪的游戏
题目：
《爱与愁的故事第三弹·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的步数
输入输出样例
输入 #1
12 16
18 10
输出 #1
8
9
说明/提示
100%数据：x1,y1,x2,y2<=20
本博客给出本题截图：
AC代码
#include <iostream> #include <algorithm> #include <cstring> #define x first #define y second using namespace std; typedef pair <int, int> PII; const int N = 100, M = N * N; PII q[M]; bool st[N][N]; int dist[N][N]; int x1, y1, x2, y2; int bfs(int sx, int sy) { int dx[12] = {-2, -2, -1, 1, 2, 2, 2, 2, 1, -1, -2, -2}; int dy[12] = {1, 2, 2, 2, 2, 1, -1, -2, -2, -2, -2, -1}; memset(st, false, sizeof st); memset(dist, 0, sizeof dist); if (sx == 1 && sy == 1) return 0; int hh = 0, tt = 0; q[0] = {sx, sy}; st[sx][sy] = true; while (hh <= tt) { auto t = q[hh ++]; for (int i = 0; i < 12; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; if (a < 1 || a > 100 || b < 1 || b > 100) continue; if (st[a][b]) continue; st[a][b] = true; dist[a][b] = dist[t.x][t.y] + 1; if (a == 1 && b == 1) return dist[a][b]; q[++ tt] = {a, b}; } } return -1; } int main() { cin >> x1 >> y1; cout << bfs(x1, y1) << endl; cin >> x2 >> y2; cout << bfs(x2, y2) << endl; return 0; }
当然我们不用st数组其实也是可以的
#include <iostream> #include <algorithm> #include <cstring> #define x first #define y second using namespace std; typedef pair <int, int> PII; const int N = 100, M = N * N; PII q[M]; int dist[N][N]; int x1, y1, x2, y2; int bfs(int sx, int sy) { int dx[12] = {-2, -2, -1, 1, 2, 2, 2, 2, 1, -1, -2, -2}; int dy[12] = {1, 2, 2, 2, 2, 1, -1, -2, -2, -2, -2, -1}; memset(dist, -1, sizeof dist); if (sx == 1 && sy == 1) return 0; int hh = 0, tt = 0; q[0] = {sx, sy}; while (hh <= tt) { auto t = q[hh ++]; for (int i = 0; i < 12; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; if (a < 1 || a > 100 || b < 1 || b > 100) continue; if (dist[a][b] != -1) continue; dist[a][b] = dist[t.x][t.y] + 1; if (a == 1 && b == 1) return dist[a][b] + 1; q[++ tt] = {a, b}; } } return -1; } int main() { cin >> x1 >> y1; cout << bfs(x1, y1) << endl; cin >> x2 >> y2; cout << bfs(x2, y2) << endl; return 0; }
总结
bfs板子题，这个题比较狗，没有给棋盘范围，开20的话只能过3个数据，50过8个数据，100才能去全过
