博客

1455.Solitaire（bfs状态混摇）

  • Post author:
  • Post category:其他


Solitaire



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





Problem Description
Solitaire is a game played on a chessboard 8×8. 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 


  1 #include<stdio.h>
  2 #include<queue>
  3 #include<string.h>
  4 #include<math.h>
  5 #include<algorithm>
  6 typedef long long ll ;
  7 bool vis[8][8][8][8][8][8][8][8] ;
  8 int move[][2] = {{1,0} , {-1,0} , {0,1} , {0,-1}} ;
  9 struct no
 10 {
 11     int x , y ;
 12 } ee[4] ;
 13 
 14 bool cmp (const no a , const no b)
 15 {
 16     if (a.x < b.x) {
 17         return true ;
 18     }
 19     else if (a.x == b.x) {
 20         if (a.y < b.y) return true ;
 21         else return false ;
 22     }
 23     else return false ;
 24 }
 25 
 26 struct node
 27 {
 28     int a[4][2] ;
 29     int step ;
 30 };
 31 node st , end ;
 32 
 33 bool bfs ()
 34 {
 35     node ans , tmp ;
 36     no rr[4] ;
 37     std::queue <node> q ;
 38     while ( !q.empty ()) q.pop () ;
 39     st.step = 0 ;
 40     q.push (st) ;
 41     while ( !q.empty ()) {
 42         ans = q.front () ; q.pop () ;
 43         for (int i = 0 ; i < 4 ; i ++) {
 44             for (int j = 0 ; j < 4 ; j ++) {
 45                 tmp = ans ;
 46                 int x = tmp.a[i][0] + move[j][0] , y = tmp.a[i][1] + move[j][1] ;
 47                 if (x < 0 || y < 0 || x >= 8 || y >= 8) continue ;
 48                 bool flag = 0 ;
 49                 for (int i = 0 ; i < 4 ; i ++ ) {
 50                     if (x == tmp.a[i][0] && y == tmp.a[i][1])
 51                         flag = 1 ;
 52                 }
 53                 if (flag ) {
 54                     x += move[j][0] , y += move[j][1] ;
 55                     if (x < 0 || y < 0 || x >= 8 || y >= 8) continue ;
 56                     for (int i = 0 ; i < 4 ; i ++) {
 57                         if (x == tmp.a[i][0] && y == tmp.a[i][1])
 58                             flag = 0 ;
 59                     }
 60                     if ( !flag ) continue ;
 61                 }
 62                 tmp.step ++ ;
 63                 if (tmp.step > 8) continue ;
 64                 tmp.a[i][0] = x , tmp.a[i][1] = y ;
 65                 if ( vis[tmp.a[0][0]] [tmp.a[0][1]] [tmp.a[1][0]] [tmp.a[1][1]] [tmp.a[2][0]] [tmp.a[2][1]] [tmp.a[3][0]] [tmp.a[3][1]]) continue;
 66                 vis[tmp.a[0][0]] [tmp.a[0][1]] [tmp.a[1][0]] [tmp.a[1][1]] [tmp.a[2][0]] [tmp.a[2][1]] [tmp.a[3][0]] [tmp.a[3][1]] = 1 ;
 67                 int cnt = 0 ;
 68                 for (int i = 0 ; i < 4 ; i ++) {
 69                     rr[i].x = tmp.a[i][0] ; rr[i].y = tmp.a[i][1] ;
 70                 }
 71                 std::sort (rr , rr + 4 , cmp ) ;
 72               /*  for (int i = 0 ; i < 4 ; i ++) {
 73                     printf ("(%d , %d) , " , rr[i].x , rr[i].y ) ;
 74                 } puts ("") ; */
 75                 for (int i = 0 ; i < 4 ; i ++) {
 76                     if (rr[i].x != ee[i].x || rr[i].y != ee[i].y )
 77                         cnt ++ ;
 78                 }
 79                 if ( ! cnt ) return true ;
 80                 if (tmp.step + cnt > 9) continue ;
 81                 q.push (tmp) ;
 82                // printf ("step = %d\n" , tmp.step ) ;
 83             }
 84         }
 85     }
 86     return false ;
 87 }
 88 
 89 int main ()
 90 {
 91     //freopen ("a.txt" , "r" , stdin ) ;
 92     while ( ~ scanf ("%d%d" , &st.a[0][0] , &st.a[0][1])) {
 93         st.a[0][0] -- ; st.a[0][1] -- ;
 94         memset (vis , 0 , sizeof(vis)) ;
 95         for (int i = 1 ; i < 4 ; i ++) for (int j = 0 ; j < 2 ; j ++) { scanf ("%d" , &st.a[i][j]) ; st.a[i][j] -- ;}
 96         for (int i = 0 ; i < 4 ; i ++) for (int j = 0 ; j < 2 ; j ++) { scanf ("%d" , &end.a[i][j]) ; end.a[i][j] -- ;}
 97         for (int i = 0 ; i < 4 ; i ++) {
 98             ee[i].x = end.a[i][0] , ee[i].y = end.a[i][1] ;
 99         }
100     // std::sort (ss , ss + 4 , cmp ) ;
101         std::sort (ee , ee + 4 , cmp ) ;
102         if ( bfs ()) puts ("YES") ;
103         else puts ("NO") ;
104     }
105     return 0 ;
106 }


View Code

四枚棋子彼此不可分，所以对每次个状态因进行一下操作，比如说排序。

转载于:https://www.cnblogs.com/get-an-AC-everyday/p/4503202.html