【程序设计大赛刷题记录】C语言 06

【奇数码问题】
连接：https://ac.nowcoder.com/acm/contest/1001/F
来源：牛客网c++

你必定玩过八数码游戏，它其实是在一个33的网格中进行的，1个空格和1~8这8个数字刚好不重不漏地分布在这33的网格中。
例如：
5 2 8
1 3 _
4 6 7
在游戏过程当中，能够把空格与其上、下、左、右四个方向之一的数字交换（若是存在）。
例如在上例中，空格可与左、上、下面的数字交换，分别变成：
5 2 8 5 2 _ 5 2 8
1 _ 3 1 3 8 1 3 7
4 6 7 4 6 7 4 6 _web

奇数码游戏是它的一个扩展，在一个n\times nn×n的网格中进行，其中n为奇数，1个空格和1\sim n\times n-11∼n×n−1这n\times n-1n×n−1个数刚好不重不漏地分布在n*n的网格中。
空格移动的规则与八数码游戏相同，实际上，八数码就是一个n=3的奇数码游戏。
如今给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面能够变化到另外一个局面。
【代码】数组

#include<bits/stdc++.h>
using namespace std;
vector <int> a[2];
int c[500500];
int ans;
void merge(vector <int> &a,int l,int mid,int r)  //运用vector的数据结构
{
    int i=l,j=mid+1;  //定义i，j

    for(int k=l;k<=r;k++){
        if(j>r||i<=mid&&a[i]<=a[j]) c[k]=a[i++];  //若是j<r或i<mid而且a[i]小于等于a[j],将a[i]数组复制到数组c[k]中
        else c[k]=a[j++],ans+=mid-i+1;
    }

    for(int k=l;k<=r;k++) a[k]=c[k];  //将c[k]复制到a[k]中
}
void guibing(vector <int> &a,int l,int r)
{
    if(l>=r) return;  //若是l大于r，函数输入错误
    int mid=(l+r)>>1;
    guibing(a,l,mid);
    guibing(a,mid+1,r);
    merge(a,l,mid,r);  //调用merge（）函数//
}
int cal(int k)
{
    ans=0;
    guibing(a[k],0,a[k].size()-1);  //调用guibing（）函数
    return ans;
}
int main()
{
    int n;
    while(cin>>n){
        a[0].clear();  //清空数据
        a[1].clear();

        for(int i=1,u;i<=n*n;i++){
            cin>>u;
            if(u) a[0].push_back(u);  //尾部加入一个数据
        }
        for(int i=1,u;i<=n*n;i++){
            cin>>u;
            if(u) a[1].push_back(u);
        }

        puts(a[0].size()&&(cal(1) - cal(0) & 1) ? "NIE" : "TAK");  //判断输出“NIE”或“TAK”

        //cout<<"ans="<<cal(0)<<endl;  //经过对函数cal（）的调用实现对前面两个子函数的调用，输出答案

    }
    return 0;
}