hdu1401：Solitaire

hdu1401：Solitaire

这是一道双向广搜的题目。

思想就是从初始状态走四步，结果往前走四步，如果这两个步骤走到状态相同的位置则说明有解。

实现如下所示：

//#include<bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<list>
#include<vector>
#include<string>
#include<iostream>
#include<ctime>
#include <cstring>
#include<math.h>
#include<algorithm>
using namespace std;struct point{int x,y;friend bool operator < (point a,point b){if (a.x!=b.x){return a.x<b.x;}return a.y<b.y;}
};struct node{point s[4];int step;
};char hs[8][8][8][8][8][8][8][8];
queue<node> q1, q2;
int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};void setflag(node a, char k){hs[a.s[0].x][a.s[0].y][a.s[1].x][a.s[1].y][a.s[2].x][a.s[2].y][a.s[3].x][a.s[3].y]=k;
}char getflag(node a){return hs[a.s[0].x][a.s[0].y][a.s[1].x][a.s[1].y][a.s[2].x][a.s[2].y][a.s[3].x][a.s[3].y];
}bool judge(node &t, int i, int j, int m){if (m==1){if (t.step>=4){return false;}t.step++;}t.s[i].x += d[j][0];t.s[i].y += d[j][1];if (t.s[i].x>=0 && t.s[i].x<8 && t.s[i].y>=0 && t.s[i].y<8){int k=0;for (k = 0; k < 4; ++k) {if (i!=k){if (t.s[i].x==t.s[k].x && t.s[i].y==t.s[k].y){if (m==1) return judge(t,i,j,2);//多走一步else return false;}}}if (k>=4){sort(t.s, t.s+4);return true;}}return false;
}bool dbfs(){int i,j;char k;node u;while (!q1.empty() || !q2.empty()){if (!q1.empty()){for (i = 0; i < 4; ++i) {for (j = 0; j < 4; ++j) {u=q1.front();if (judge(u,i,j,1)){k= getflag(u);if (k==2) return true;else if (k==0){sort(u.s,u.s+4);setflag(u, 1);q1.push(u);}}}}q1.pop();}if (!q2.empty()){for (i = 0; i < 4; ++i) {for (j = 0; j < 4; ++j) {u=q2.front();if (judge(u,i,j,1)){k= getflag(u);if (k==1) return true;else if (k==0){sort(u.s,u.s+4);setflag(u, 2);q2.push(u);}}}}q2.pop();}}return false;
}int main(){int i,j;node A,B;while (scanf("%d%d", &i, &j)!=EOF){memset(hs,0,sizeof(hs));while (!q1.empty()) q1.pop();while (!q2.empty()) q2.pop();i--,j--;A.s[0].x=i,A.s[0].y=j;A.step=0;for (i = 1; i < 4; ++i) {scanf("%d%d",&A.s[i].x,&A.s[i].y);A.s[i].x--, A.s[i].y--;}sort(A.s,A.s+4);setflag(A, 1);for (i = 0; i < 4; ++i) {scanf("%d%d",&B.s[i].x,&B.s[i].y);B.s[i].x--, B.s[i].y--;}sort(B.s,B.s+4);setflag(B, 2);B.step=0;q1.push(A);q2.push(B);if (dbfs()){printf("YESn");}else{printf("NOn");}}return 0;
}