首页 > 代码库 > POJ 2893 M × N Puzzle(树状数组求逆序对)

POJ 2893 M × N Puzzle(树状数组求逆序对)

                                                           M × N Puzzle
Time Limit: 4000MS   Memory Limit: 131072K
Total Submissions: 4112   Accepted: 1140

Description

The Eight Puzzle, among other sliding-tile puzzles, is one of the famous problems in artificial intelligence. Along with chess, tic-tac-toe and backgammon, it has been used to study search algorithms.

The Eight Puzzle can be generalized into an M × N Puzzle where at least one of M and N is odd. The puzzle is constructed with MN ? 1 sliding tiles with each a number from 1 to MN ? 1 on it packed into a M by N frame with one tile missing. For example, with M = 4 and N = 3, a puzzle may look like:

1 6 2
4 0 3
7 5 9
10 8 11

Let‘s call missing tile 0. The only legal operation is to exchange 0 and the tile with which it shares an edge. The goal of the puzzle is to find a sequence of legal operations that makes it look like:

1 2 3
4 5 6
7 8 9
10 11 0

The following steps solve the puzzle given above.

START

1 6 2
4 0 3
7 5 9
10 8 11

DOWN
?

1 0 2
4 6 3
7 5 9
10 8 11
LEFT
?
1 2 0
4 6 3
7 5 9
10 8 11

UP
?

1 2 3
4 6 0
7 5 9
10 8 11

 

RIGHT
?

1 2 3
4 0 6
7 5 9
10 8 11

UP
?

1 2 3
4 5 6
7 0 9
10 8 11
UP
?
1 2 3
4 5 6
7 8 9
10 0 11

LEFT
?

1 2 3
4 5 6
7 8 9
10 11 0

GOAL

Given an M × N puzzle, you are to determine whether it can be solved.

Input

The input consists of multiple test cases. Each test case starts with a line containing M and N (2 M, N ≤ 999). This line is followed by M lines containing N numbers each describing an M × N puzzle.

The input ends with a pair of zeroes which should not be processed.

Output

Output one line for each test case containing a single word YES if the puzzle can be solved and NO otherwise.

Sample Input

3 3
1 0 3
4 2 5
7 8 6
4 3
1 2 5
4 6 9
11 8 10
3 7 0
0 0

Sample Output

YES
NO

题意:8数码问题的升级,就是通过移动空格(用0代替)使得原来状态变成有序的1234......0,不过,这题是N*M数码。

题解:N*M都挺大的,搜索必然不行。考虑终态,实际就是逆序数为0的状态,然后四种操作方式分为:左右移动,对原序列的逆序数不影响;上下移动,如下:

-------------0***********

***********x-------------

x是任意数,现在要把x移上去,那么***********中,假设有a个大于x,b个小于x,那么移动之后逆序数就会加上一个b-a,x所能影响的也就是这些罢了,除此之外,其他都不变。

接着,如果列数为偶数,那么******的个数就是奇数,b,a奇偶性互异,b-a为奇数,所以移动一次后,原序列的逆序数的奇偶性变了。

考虑到最后0会移动到最后一行,所以奇偶性会改变n-i次(i为0的行数),只需判断最后是否是偶数即可。

反之,如果列数为奇数,那么******的个数就是偶数,b,a奇偶性相同,b-a为偶数,所以移动一次后,原序列的逆序数的奇偶性没变。

因为无论怎么移,奇偶性都不变,所以说一开始初态的奇偶性就必须与末态一致。

题意来自http://blog.csdn.net/tmeteorj/article/details/8530105

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 2e9
#define met(a,b) memset(a,b,sizeof a)
typedef long long ll;
using namespace std;
const int N = 999*999+5;
const int M = 4e5+5;
int n,m,tot=0,cnt=0;
int head[N],ans[N];
int tree[N];
int a[N];
void add(int k,int num) {
    while(k<=999*999-1) {
        tree[k]+=num;
        k+=k&(-k);
    }
}
int Sum(int k) {
    int sum=0;
    while(k>0) {
        sum+=tree[k];
        k-=k&(-k);
    }
    return sum;
}
int main() {

    while(scanf("%d%d",&n,&m),n||m) {
        int x,y,t,s=0,nu=0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++) {
                scanf("%d",&t);
                if(t==0)
                    x=i,y=j;
                else
                    a[nu++]=t;
            }
       met(tree,0);
        for(int i=nu-1; i>=0; i--) {
            s+=Sum(a[i]-1);
            add(a[i],1);
        }
        if(m&1)
            if(s&1)puts("NO");
            else   puts("YES");
        else if(((n-x)^s)&1) puts("NO");
        else            puts("YES");
    }
    return 0;
}

 

POJ 2893 M × N Puzzle(树状数组求逆序对)