Solitaire

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2944 Accepted Submission(s): 915

Problem Description Solitaire is a game played on a chessboard 8x8. The rows and columns of the chessboard are numbered from 1 to 8, from the top to the bottom and from left to right respectively.

There are four identical pieces on the board. In one move it is allowed to:

> move a piece to an empty neighboring field (up, down, left or right),

> jump over one neighboring piece to an empty field (up, down, left or right).

There are 4 moves allowed for each piece in the configuration shown above. As an example let's consider a piece placed in the row 4, column 4. It can be moved one row up, two rows down, one column left or two columns right.

Write a program that:

> reads two chessboard configurations from the standard input,

> verifies whether the second one is reachable from the first one in at most 8 moves,

> writes the result to the standard output.

Input Each of two input lines contains 8 integers a1, a2, ..., a8 separated by single spaces and describes one configuration of pieces on the chessboard. Integers a2j-1 and a2j (1 <= j <= 4) describe the position of one piece - the row number and the column number respectively. Process to the end of file.

Output The output should contain one word for each test case - YES if a configuration described in the second input line is reachable from the configuration described in the first input line in at most 8 moves, or one word NO otherwise.

Sample Input

4 4 4 5 5 4 6 5
2 4 3 3 3 6 4 6

Sample Output

YES

Source Southwestern Europe 2002

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int dir_x[4]={-1,1,0,0}; const int dir_y[4]={0,0,-1,1}; bool inside(int x,int y) { if((x>=1&&x<=8)&&(y>=1&&y<=8)) return true; return false; } struct POINT { int x,y; bool operator<(const POINT& res) const { if(x!=res.x) return x
        
          panchong; struct NODE { int id,ti; }; int doit(int xx,int yy,int hs) { POINT rk[4]; int u=hs; for(int i=3;i>=0;i--) { rk[i].y=u%10; u/=10; rk[i].x=u%10; u/=10; } int x=rk[xx].x,y=rk[xx].y; int X=x+dir_x[yy],Y=y+dir_y[yy]; if(inside(X,Y)==false) return -1; bool flag=false; for(int i=0;i<4;i++) if(rk[i].x==X&&rk[i].y==Y) { flag=true; break; } if(flag==true) { int X2=X+dir_x[yy],Y2=Y+dir_y[yy]; if(inside(X2,Y2)==false) return -1; bool flag2=false; for(int i=0;i<4;i++) if(rk[i].x==X2&&rk[i].y==Y2) { flag2=true; break; } if(flag2==true) return -1; rk[xx].x=X2;rk[xx].y=Y2; } else { rk[xx].x=X;rk[xx].y=Y; } sort(rk,rk+4); return hahashsh(rk); } void zBFS(int ss) { queue
         
           q; q.push((NODE){ss,0}); while(!q.empty()) { NODE u,v; u=q.front();q.pop(); if(u.ti+1>4) continue; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { ///4个棋子4个方向 int temp=doit(i,j,u.id); if(temp==-1) continue; if(panchong.count(temp)==0) { panchong.insert(temp); q.push((NODE){temp,u.ti+1}); } } } } } int fBFS(int es) { queue
          
            q; set
           
             fafa; fafa.clear(); fafa.insert(es); q.push((NODE){es,0}); while(!q.empty()) { NODE u,v; u=q.front(); q.pop(); if(u.ti+1>4) continue; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { ///4个棋子4个方向 int temp=doit(i,j,u.id); if(temp==-1) continue; if(panchong.count(temp)) return 1; if(fafa.count(temp)==0) { fafa.insert(temp); q.push((NODE){temp,u.ti+1}); } } } } return 0; } int solve(int ss,int es) { zBFS(ss); return fBFS(es); } int main() { while(scanf(%d%d,&st[0].x,&st[0].y)!=EOF) { for(int i=1;i<4;i++) scanf(%d%d,&st[i].x,&st[i].y); for(int i=0;i<4;i++) scanf(%d%d,&ed[i].x,&ed[i].y); sort(st,st+4);sort(ed,ed+4); panchong.clear(); panchong.insert(hahashsh(st)); if(solve(hahashsh(st),hahashsh(ed))) puts(YES); else puts(NO); } return 0; }

HDOJ 1401 Solitaire

Solitaire