1 /*
2 * SOUR:sgu139
3 * ALGO:8数码问题的推广
4 * DATE: 2009年 12月 25日 星期五 21:37:54 CST
5 * COMM:4http://www.cppblog.com/schindlerlee
6 * */
7 #include<iostream>
8 #include<cstdio>
9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 using namespace std;
13 typedef long long LL;
14 const int maxint = 0x7fffffff;
15 const long long max64 = 0x7fffffffffffffffll;
16
17 const int N = 16;
18 int num[N];
19 int main()
20 {
21 //最终状态 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
22 //逆序数15
23 int i,j,offset = 0;
24 int inver = 0;
25 for(i = 0;i < N;i++) {
26 scanf("%d",num + i);
27 if(num[i] == 0) {
28 offset += 3 - (i / 4);
29 offset += 3 - (i % 4);
30 }
31 }
32 for(i = 1;i < N;i++) {
33 for(j = i - 1;j >= 0;j--) {
34 if(num[j] > num[i]) {
35 inver ++;
36 }
37 }
38 }
39 //维度为偶数的这种问题，会改变会改变数列的逆序奇偶性,所以还要判断哈密顿距离的奇偶
40 //维度为奇数的这种问题，则只需要判断逆序的奇偶性
41 //奇偶性相同且offset为偶 或
42 //奇偶性不同且offset为奇 这样的状态都能互相到达
43 if((inver % 2 == 1) == (offset % 2 == 0)) {
44 puts("YES");
45 }else {
46 puts("NO");
47 }
48 return 0;
49 }
50
51
52