纸牌游戏是在8x8的棋盘上进行的游戏。棋盘的行和列的编号分别为1到8，从上到下，从左到右。
板上有四个相同的部分。一键操作允许：
将一块移到一个空的相邻字段（上，下，左或右），
跳过一块相邻的棋子到一个空白字段（上，下，左或右）。
在上面显示的配置中，每件允许进行4次移动。作为示例，让我们考虑放置在第4行第4列中的片段。它可以上移，下移两行，左移一列或右移两列。
编写一个程序，该程序：
从标准输入中读取两个棋盘配置，
验证最多八个动作中第一个棋盘是否可以到达第二个棋盘配置，
将结果写入标准输出。
两行输入中的每行包含8个由单个空格分隔的整数a1，a2，…，a8，并描述了棋the上棋子的一种配置。整数a2j-1和a2j（1 <= j <= 4）描述一件的位置-分别是行号和列号。处理到文件末尾。
对于每个测试用例，输出应包含一个单词-如果在第二输入行中描述的配置最多可以在8个动作中到达第一输入行中描述的配置，则为“是”，否则为“否”。
这道题是一个标准的双向广搜题目，思路蛮简单的，就标准的两边搜，然后满足条件退出。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #define vis(tail) vis[(int)tail.t[0].x][(int)tail.t[0].y][(int)tail.t[1].x][(int)tail.t[1].y][(int)tail.t[2].x][(int)tail.t[2].y][(int)tail.t[3].x][(int)tail.t[3].y] using namespace std; char vis[8][8][8][8][8][8][8][8]; int dx[4]={-1, 0, 0, 1}; int dy[4]={0, -1, 1, 0}; struct node{ int x, y; }; struct Node{ node t[4]; int step; }front,tail; bool comp(node &a, node &b){ if(a.x == b.x) return a.y < b.y; return a.x < b.x; } queue < Node > q; // 0 1 2 3 // 0 -> 1, 1 -> 2, 2 -> 3, 3 -> 4; // 8 -> 7, 7 -> 6, 6 -> 5, 5 -> 4; void bfs(){ while(!q.empty()){ front = q.front();q.pop(); if(front.step > 3){ printf("NO\n"); return; } for(int i = 0; i < 4; i++){ for(int k = 0; k < 4; k++){ tail = front; tail.t[i].x = tail.t[i].x + dx[k]; tail.t[i].y = tail.t[i].y + dy[k]; bool flag = false; int cnt = 0; while(!flag && cnt <= 1){ if(tail.t[i].x >= 0 && tail.t[i].x < 8 && tail.t[i].y >= 0 && tail.t[i].y < 8){ flag = true; } for(int j = 0; j < 4; j++){ if(i == j) continue; if(tail.t[i].x == tail.t[j].x && tail.t[i].y == tail.t[j].y){ flag = false; break; } } if(!flag && cnt < 1){ tail.t[i].x = tail.t[i].x + dx[k]; tail.t[i].y = tail.t[i].y + dy[k]; } cnt++; } //cout<<"tail: "<<tail.t[0].x<<" "<<tail.t[0].y<<" "<<tail.t[1].x<<" "<<tail.t[1].y<<" "<<tail.t[2].x<<" "<<tail.t[2].y<<" "<<tail.t[3].x<<" "<<tail.t[3].y<<endl; if(flag){ sort(tail.t, tail.t + 4, comp); if((int)vis(tail) == 0){ vis(tail) = vis(front); tail.step = front.step + 1; q.push(tail); }else if((int)vis(tail) != (int)vis(front)){ printf("YES\n"); return; } } } } } } int main(){ while(scanf("%d%d", &front.t[0].x, &front.t[0].y) != EOF){ memset(vis, 0, sizeof(vis)); while(!q.empty()) q.pop(); front.t[0].x--;front.t[0].y--; for(int i = 1; i < 4; i++){ scanf("%d%d", &front.t[i].x, &front.t[i].y);front.t[i].x--;front.t[i].y--; } front.step = 0; sort(front.t, front.t + 4, comp); vis(front) = 1; q.push(front); for(int i = 0; i < 4; i++){ scanf("%d%d", &front.t[i].x, &front.t[i].y);front.t[i].x--;front.t[i].y--; } front.step = 0; sort(front.t, front.t + 4, comp); if(vis(front) == 1){ printf("YES\n"); continue; } vis(front) = 2; q.push(front); bfs(); } }