hdu 4021 24 Puzzle ( 逆序数判断是否可解 )

24 PuzzleTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)Total Submission(s): 1306    Accepted Submission(s): 381

Problem Description
  The ‘#’ denotes the positions that the tiles may be placed on. There are 24 possible positions in total, so one of them is not occupied by the tile. We can denote the empty position by zero.
  Daniel could move the tiles to the empty position if the tile is on the top, bottom, left or right of the empty position. In this way Daniel can reorder the tiles on the board.
Usually he plays with this game by setting up a target states initially, and then trying to do a series of moves to achieve the target. Soon he finds that not all target states could be achieved.
  He asks for your help, to determine whether he has set up an impossible target or not.
InputOutputSample InputSample OutputSource#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 30#define MAXN 20005#define mod 1000000007#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 0.000001typedef long long ll;using namespace std;int n,m,ans,p1,p2;int a[maxn],b[maxn];int mp[maxn];bool presolve(){ int i,j; if(a[0]==0) swap(a[0],a[3]); if(a[1]==0) swap(a[1],a[6]); if(a[2]==0) swap(a[2],a[3]); if(a[7]==0) swap(a[7],a[6]); if(a[16]==0) swap(a[16],a[17]); if(a[21]==0) swap(a[21],a[20]); if(a[22]==0) swap(a[22],a[17]); if(a[23]==0) swap(a[23],a[20]); if(b[0]==0) swap(b[0],b[3]); if(b[1]==0) swap(b[1],b[6]); if(b[2]==0) swap(b[2],b[3]); if(b[7]==0) swap(b[7],b[6]); if(b[16]==0) swap(b[16],b[17]); if(b[21]==0) swap(b[21],b[20]); if(b[22]==0) swap(b[22],b[17]); if(b[23]==0) swap(b[23],b[20]); for(i=0;i<24;i++) { if(a[i]==0) p1=i; if(b[i]==0) p2=i; } if(a[0]!=b[0]||a[1]!=b[1]||a[2]!=b[2]||a[7]!=b[7]|| a[16]!=b[16]||a[21]!=b[21]||a[22]!=b[22]||a[23]!=b[23]) return false ; return true ;}int getstate(int x[]){ int i,j,t,s,sum=0; for(i=3;i<24;i++) { t=x[i]; if(t==0||i==7||i==16||i==21||i==22||i==23) continue ; s=0; for(j=i+1;j<24;j++) { if(x[j]==0||j==7||j==16||j==21||j==22||j==23) continue ; if(x[j]<t) s++; } sum+=s; } return sum;}int main(){ int i,j,t,s1,s2; mp[3]=mp[4]=mp[5]=mp[6]=1; mp[8]=mp[9]=mp[10]=mp[11]=2; mp[12]=mp[13]=mp[14]=mp[15]=3; mp[17]=mp[18]=mp[19]=mp[20]=4; scanf("%d",&t); while(t--) { for(i=0;i<24;i++) { scanf("%d",&a[i]); } for(i=0;i<24;i++) { scanf("%d",&b[i]); } if(presolve()) { s1=getstate(a); s2=getstate(b); if((s1+s2)&1) { if(abs(mp[p1]-mp[p2])&1) printf("N\n"); else printf("Y\n"); } else { if(!(abs(mp[p1]-mp[p2])&1)) printf("N\n"); else printf("Y\n"); } } else printf("Y\n"); } return 0;}