2015
04-15

# 24 Puzzle

Daniel likes to play a special board game, called 24 puzzle. 24 puzzle is such a game that there are tiles with the number 1 to 23 in a play board like the follow picture:

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.

The first line of input contains an integer denoting the number of test cases.
For each test case, the first line contains 24 integers denoting the initial states of the game board. The numbers are the describing the tiles from top to bottom, left to right. And the empty position is indicated by zero. You can assume that the number of each tile are different, and there must be exactly one empty position. The second line of test case also contains 24 integers denoting the target states.

The first line of input contains an integer denoting the number of test cases.
For each test case, the first line contains 24 integers denoting the initial states of the game board. The numbers are the describing the tiles from top to bottom, left to right. And the empty position is indicated by zero. You can assume that the number of each tile are different, and there must be exactly one empty position. The second line of test case also contains 24 integers denoting the target states.

2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
3 1 2 0 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
3 0 2 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

N
Y

#include<stdio.h>
#include<algorithm>
using namespace std;
int n,q[]={0,1,3,2,8,17,23,22,24},e[]={0,4,4,7,7,18,18,21,21};
int abs(int x){
return x>0?x:(-x);
}
int main(){
scanf("%d",&n);
while(n--){
int begin[33],end[33];
for(int i=1;i<=24;i++)
scanf("%d",&begin[i]);
for(int i=1;i<=24;i++)
scanf("%d",&end[i]);
for(int i=1;i<=8;i++){
if(begin[q[i]]==0)
swap(begin[q[i]],begin[e[i]]);
if(end[q[i]]==0)
swap(end[q[i]],end[e[i]]);
}
bool flag=0;
for(int i=1;i<=8;i++){
if(begin[q[i]]!=end[q[i]]){
flag=1;
break;
}
}
if(flag){
printf("Y\n");
continue;
}
int n1=0,n2=0,m_pos1=0,m_pos2=0;
int a[33],b[33],sum1=0,sum2=0;
for(int i=1;i<=24;i++){
flag=0;
for(int j=1;j<=8;j++)
if(i==q[j])
flag=1;
if(flag)continue;
a[sum1++]=begin[i];
}
for(int i=1;i<=24;i++){
flag=0;
for(int j=1;j<=8;j++)
if(i==q[j])
flag=1;
if(flag)continue;
b[sum2++]=end[i];
}
for(int i=1;i<sum1;i++){
if(a[i]==0)
m_pos1=i;
else{
for(int j=0;j<i;j++){
if(a[i]<a[j])
n1++;
}
}
}
for(int i=1;i<sum2;i++){
if(b[i]==0)
m_pos2=i;
else{
for(int j=0;j<i;j++){
if(b[i]<b[j])
n2++;
}
}
}
int it=abs(m_pos1/4-m_pos2/4);
if(abs(it+n1-n2)%2==0)
printf("N\n");
else
printf("Y\n");
}
return 0;
}


1. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

2. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

3. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

4. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

5. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

6. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

7. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

8. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

9. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

10. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

11. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

12. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

13. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

14. 当时用短剑主要还是材料不行，青铜合金太软或太脆，剑身长了就容易断或者变形什么的，到后来铁越来越流行了，剑就越来越长了。

15. 小米之所以受欢迎，除了吹捧的硬件之外。更主要的MIUI这个系统。如果系统不能做好，光有硬件有什么用，等把使用体验优化到很好了，再说收费吧。模仿苹果不是光模仿她的收费模式，你也模仿下他的系统优化啊，主频不高，但性能很好。

16. 小米之所以受欢迎，除了吹捧的硬件之外。更主要的MIUI这个系统。如果系统不能做好，光有硬件有什么用，等把使用体验优化到很好了，再说收费吧。模仿苹果不是光模仿她的收费模式，你也模仿下他的系统优化啊，主频不高，但性能很好。

17. 小米之所以受欢迎，除了吹捧的硬件之外。更主要的MIUI这个系统。如果系统不能做好，光有硬件有什么用，等把使用体验优化到很好了，再说收费吧。模仿苹果不是光模仿她的收费模式，你也模仿下他的系统优化啊，主频不高，但性能很好。

18. 小米之所以受欢迎，除了吹捧的硬件之外。更主要的MIUI这个系统。如果系统不能做好，光有硬件有什么用，等把使用体验优化到很好了，再说收费吧。模仿苹果不是光模仿她的收费模式，你也模仿下他的系统优化啊，主频不高，但性能很好。

19. 小米之所以受欢迎，除了吹捧的硬件之外。更主要的MIUI这个系统。如果系统不能做好，光有硬件有什么用，等把使用体验优化到很好了，再说收费吧。模仿苹果不是光模仿她的收费模式，你也模仿下他的系统优化啊，主频不高，但性能很好。

20. 小米之所以受欢迎，除了吹捧的硬件之外。更主要的MIUI这个系统。如果系统不能做好，光有硬件有什么用，等把使用体验优化到很好了，再说收费吧。模仿苹果不是光模仿她的收费模式，你也模仿下他的系统优化啊，主频不高，但性能很好。

21. 小米之所以受欢迎，除了吹捧的硬件之外。更主要的MIUI这个系统。如果系统不能做好，光有硬件有什么用，等把使用体验优化到很好了，再说收费吧。模仿苹果不是光模仿她的收费模式，你也模仿下他的系统优化啊，主频不高，但性能很好。

22. 小米之所以受欢迎，除了吹捧的硬件之外。更主要的MIUI这个系统。如果系统不能做好，光有硬件有什么用，等把使用体验优化到很好了，再说收费吧。模仿苹果不是光模仿她的收费模式，你也模仿下他的系统优化啊，主频不高，但性能很好。