HDU 6620 Just an Old Puzzle

You are given a 4 × 4 grid, which consists of 15 number cells and an empty cell.
All numbers are unique and ranged from 1 to 15.
In this board, the cells which are adjacent with the empty cell can move to the empty cell.
Your task is to make the input grid to the target grid shown in the figure below.
In the following example (sample input), you can get the target grid in two moves.

Input
The first line contains an integer T (1 <= T <= 10^5) denoting the number of test cases.
Each test case consists of four lines each containing four space-separated integers, denoting the input grid. 0 indicates the empty cell.

Output
For each test case, you have to print the answer in one line.
If you can’t get the target grid within 120 moves, then print 'No', else print 'Yes'.

Sample Input
2
1 2 3 4
5 6 7 8
9 10 0 12
13 14 11 15
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 0

Sample Output
Yes
No

题解:
1:15数码若可以解决最坏的情况为移动80次。
2:(n为奇数)奇数码游戏两个局面可达,当且仅当两个局面下网格中的数依次写成1行 n * n - 1 个元素的序列后(不考虑空格),逆序对个数的奇偶性相同。
3:(n为偶数)此时两个局面可达,当且仅当两个局面对应网格写成序列后,“逆序对之差” 和 “两个局面下空行所在行数之差”奇偶性相同。

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

#define lowbit(x) x & (-x)
#define lson left,mid,root << 1
#define rson mid+1,right,root << 1 | 1

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=1e5+100;


int a[20];


int main()
{
    int t;
    scanf("%d",&t);
    while(t --)
        {
            int r = 0, z = 0;
            for(int i = 1; i <= 16; i ++)
                {
                    scanf("%d",&a[i]);
                    if(!a[i])
                        z = i / 4 + (i % 4 != 0); // 找空格的初始位置 
                    else
                        {
                            for(int j = 1; j < i; j ++)
                                if(a[j] > a[i])
                                    r ++;           // 逆序对个数 
                        }
                }
            if((4 - z) % 2 == (r % 2))  // 判断奇偶性 
                puts("Yes");
            else
                puts("No");
        }
    return 0;
 } 
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注