【排序】绝境求生

问题 E: 【排序】绝境求生

时间限制: 1 Sec 内存限制: 64 MB
提交: 4 解决: 4
[提交] [状态] [讨论版] [命题人:]

题目描述

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:

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:

The following steps solve the puzzle given above.

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

样例输入

样例输出

YES
NO

分析：不知道之前什么时候水过这题，去POJ抄来了题解。。。一个树状数组求逆序对的题。。

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#define range(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
#define rerange(i,a,b) for(int i=a;i>=b;--i)
#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))
using namespace std;
int n,m,tol,cnt,head[1000005],ans[1000005],tree[1000005],aa[1000005];
void init(){

}
int sum(int x){
    int sum=0;
    while(x>0){
        sum+=tree[x];
        x-=x&(-x);
    }
    return sum;
}
void add(int x,int y){
    while(x<=1000005){
        tree[x]+=y;
        x+=x&(-x);
    }
}
void solve(){
    while(cin>>n>>m,n,m){
        int x,y,t,s=0,num=0;
        range(i,1,n)range(j,1,m){
            cin>>t;
            if(!t)x=i,y=j;
            else aa[num++]=t;
        }
        fill(tree,0);
        rerange(i,num-1,0){
            s+=sum(aa[i]-1);
            add(aa[i],1);
        }
        if(m&1)cout<<(s&1?"NO":"YES")<<endl;
        else if(((n-x)^s)&1)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
}
int main() {
    init();
    solve();
    return 0;
}

View Code