M × N Puzzle – 逆序对【N*M数码问题局面之间可达性判定】

  • Post author:
  • Post category:其他



M × N Puzzle

Sol:


\(N*M\)

数码某局面到达另一局面的可行性判定

可以通过逆序对个数的奇偶性是否相同来判定。

我们将这

\(N*M-1\)

个数写成一列来看。

  • 考虑行为奇数,列为奇数的情况->逆序对个数奇偶性相同时可达

    空格左右移动不会改变逆序对的个数,而上下移动相当于改变了该列前后共

    \(M-1\)

    个数的逆序对个数,由于

    \(M-1\)

    是偶数,所以移动前后逆序对个数奇偶性不变。
  • 考虑行为奇数,列为偶数的情况->(逆序对个数+前后状态空格行数之差)奇偶性相同时可达

    上下移动会改变共

    \(M-1\)

    个数的逆序对个数,而

    \(M-1\)

    是奇数,当上下移动了偶数行时,奇偶性不变;上下移动了奇数行时,奇偶性改变。
  • 行为偶数时,同上。

    AC CODE:

Source Code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    int x=0,f=1;char ch=' ';
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
    return x*f;
}
const int N = 1000 + 2;
int n,m;
int a[N*N],tot;
int tr[N*N];
int lowbit(int x){
    return x&-x;
}
void modify(int p,int k){
    for(int i=p;i<=tot;i+=lowbit(i)){
        tr[i]+=k;
    }
}
int query(int p){
    int ans=0;
    for(int i=p;i;i-=lowbit(i)){
        ans+=tr[i];
    }
    return ans;
}
int main(){
//  freopen("data.in","r",stdin);
//  freopen("sol.out","w",stdout);
    while(1){
        n=read();m=read();
        if(!n&&!m) break;
        memset(tr,0,sizeof(tr));
        tot=0;int pos;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int x;x=read();
                if(x) a[++tot]=x;
                else pos=i;
            }
        }
        int mul=n*m;
        int ans=0;
        for(int i=tot;i;i--){
            ans+=query(a[i]-1);
            modify(a[i],1);
        }
        if(m%2==0){
            ans+=n-pos;
        }
        if(ans%2==0) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

转载于:https://www.cnblogs.com/Loi-Brilliant/p/9785056.html