1 /*
2 * SOUR:sgu139
3 * ALGO:8數碼問題的推廣
4 * DATE: 2009年 12月 25日 星期五 21:37:54 CST
5 * COMM:4http://www.shnenglu.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