分析:其实跟八数码问题差不多,用康托展开记录状态,bfs即可。

C D E F

 

个位置,用1的方法将待移动的数变换到最后一个位置。循环这样做即可。
引理三证

View Code

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdlib>
#define Mod 1000000007
#define SMod 10007
#define INint 2147483647
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define ll long long
using namespace std;
#define N 500007

struct node
{
    ll cantor,cost;
    int pos;
    bool operator <(const node& a)const
    {
        return cost > a.cost;
    }
}S,E;

priority_queue<node> que;
ll fact[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
int dx[4] = {1,-1,3,-3};
int a[11],b[11],Can[N][11],vis[N];
ll ans,ch,cv;

ll Cantor(int *a)
{
    int i,j;
    ll cnt;
    ll res = 0;
    for(i=0;i<9;i++)
    {
        cnt = 0;
        for(j=i+1;j<9;j++)
            if(a[i] > a[j])
                cnt++;
        res += cnt*fact[8-i];
    }
    return res;
}

void getcantor(ll cantor,int *a)
{
    for(int i=0;i<9;i++)
        Can[cantor][i] = a[i];
}

void geta(ll cantor)
{
    for(int i=0;i<9;i++)
        a[i] = Can[cantor][i];
}

void bfs()
{
    while(!que.empty())
        que.pop();
    memset(vis,0,sizeof(vis));
    int i,j;
    que.push(S);
    //vis[S.cantor] = 1;
    while(!que.empty())
    {
        node tmp = que.top();
        que.pop();
        ll cantor = tmp.cantor;
        ll cost = tmp.cost;
        int pos = tmp.pos;
        if(vis[cantor])
            continue;
        vis[cantor] = 1;
        if(cost >= ans)
            continue;
        if(cantor == E.cantor)
        {
            ans = min(ans,cost);
            break;
        }
        geta(cantor);
        for(int k=0;k<4;k++)
        {
            int v = (pos+dx[k]+9)%9;
            swap(a[v],a[pos]);
            ll newcantor = Cantor(a);
            if(vis[newcantor])
            {
                swap(a[v],a[pos]);
                continue;
            }
            getcantor(newcantor,a);
            swap(a[v],a[pos]);
            node now;
            now.cantor = newcantor;
            now.pos = v;
            if(k < 2)
                now.cost = cost + ch;
            else
                now.cost = cost + cv;
            if(now.cost >= ans)
                continue;
            //vis[newcantor] = 1;
            que.push(now);
        }
    }
}

int main()
{
    int i,j;
    while(scanf("%lld%lld",&ch,&cv) && (ch||cv))
    {
        for(i=0;i<9;i++)
        {
            scanf("%d",&a[i]);
            if(a[i] == 0)
                S.pos = i;
        }
        S.cantor = Cantor(a);
        S.cost = 0;
        for(i=0;i<9;i++)
            scanf("%d",&b[i]);
        E.cantor = Cantor(b);
        getcantor(S.cantor,a);
        getcantor(E.cantor,b);
        ans = (1LL<<62);
        bfs();
        printf("%lld\n",ans);
    }
    return 0;
}

 

代码:

八数码问题的有解无解的结论:

图片 1图片 2

 

题意大概就是八数码问题,只不过把空格的移动方式改变了:空格能够向前或向后移动一格或三格(循环的)。

 

一个排列。到这里,我想要得到前面的两种状态之一是显然的了。下面,我说明,上面

 

 

 

 

1 2 3 4

当N为奇数时,N-1和N^2-1均为偶数,也就是任意移动空格逆序奇偶性不变。那么逆序奇偶性相同的两个状态可相互到达。

 

 

明,抛砖引玉,如果大家发现其中有什么问题,欢迎来我宿舍一起讨论或者给我发Emai

可以证明,以上状态是一个无解的状态(将C移到了第四行)。该状态的逆序为0,和原始状态相同,但是它的空格位置在第三行。若将空格移到第四行,必然使得它的逆序±1或±3,奇偶性必然改变。所以它是一个无解的状态。

 

保持7和8不动,依次移动6,5,4,3,得到 * * * 3 4 5 6 7 8这里 * *
*是 @ 1 2 的

毕。

通过观察,得出以下结论:

 

想提一点的是,九宫图之间的变换是可逆的。下面,到了问题的核心部分了。

 

 

,也就是对于任意一对数,如果前面的数比后面的数大,则为一对逆序。对于一个序列

首先,相邻的对换肯定不改变奇偶性;其次,隔两格的对换也不改变奇偶性,它相当于

7 8

C D E F

格)。比如: 1 2 3 4 @ 5 => 1 2 3 4 @ 5 6 7 8 6 7 8 这样

 

8数码难题搜索时,有时候是无解的,8数码问题总共有9!种状态,如果用计算机一

,我们定义其逆序奇偶性如下:
如果其中有奇数对逆序,称之逆序奇;如果其中有

我们用字母A~F代替数字10~15。同样地,当左右移动的时候,状态的逆序不改变。而当上下移动的时候,相当于一个数字跨过了另外三个格子,它的逆序可能±3或±1,逆序的奇偶性必然改变。那么又该如何

5 6 7 8

所有的奇九宫图之间是可达的,所有的偶九宫图之间也是可达的,但奇九宫图和偶

 

 

假定上面两种状态之间的转换可以用行序列中的两种邻对换来代替。

9 A B C

我们将九宫格按行排成一行共九个数(空格也占一个位置,在本文种,我用@表示空

5 6 7 8

可以转换为 @ 2 1 3 4 5 6 7 8.
要证明这个引理,得分几个步骤。我的想法是先设

>推广到三维N×N×N

1 2 3 4 5 6 7 8 0

 

 

智力游戏,玩之余,我在想,能否通过事先的分析来判断哪些问题有解,哪些问题无解

引理一:在上述的两种对换下,序列的奇偶性不改变。 这个引理很容易证明。

也就是说,当此表达式成立时,两个状态可相互到达:(状态1奇偶性==状态2奇偶性)==(空格距离%2==0)。

N×N的棋盘,N为奇数时,与八数码问题相同。

讨论到这里,题目问题也就解决了。

先介绍八数码问题:

#include <stdio.h>
int a[90010],b[90010],nxs;

void mergeSort(int first,int last)
{
    int mid,i;
    int begin,m,end;
    if(first+1<last)
    {
       mid=(first+last)/2;       
       //merge(first,mid,last);
       begin=first;
       m=mid;
       i=first;
       mergeSort(first,mid);
       mergeSort(mid,last);
       while(begin<mid && m<end)
       {
          if(a[begin]<=a[m])
          {
              b[i++]=a[begin++];          
          }
          else 
          {
              b[i++]=a[m++];             
              //for(i=beginA;i<=mid;i++)
                  //printf("nixuyou:%d,%d\n",a[i],a[beginB]);
              nxs+=mid-begin;     
          }                    
       }                  
       while(begin<mid)
       {
          b[i++]=a[begin++];            
       }
       while(m<last)
       {
          b[i++]=a[m++];             
       }
       /*for(i=0;i<j;i++)
       {
          a[first+i]=b[i];                
       }*/
       while(first<last)
       {
          a[first]=b[first++];                 
       }     
    }
}


int main()
{
   int n,sum,i,iwz,hangshu,hangshucha,panduanshu,j,x;
   while(scanf("%d",&n)==1 && n)
   {
        sum=n*n;
        j=0;
        for(i=0;i<sum;i++)
        {
            scanf("%d",&x);
            if(x==0)
            {   
                iwz=i;
            }        
            else
            {
                a[j]=x;
                j++;
            }
        }
        nxs=0;
        mergeSort(0,sum-1);
        //printf("nxs=%d\n",nxs);    
        if(n%2==1) //n为奇数
        {
              if(nxs%2==0)
                   printf("YES\n");
              else 
                   printf("NO\n");         
        }
        else //n为偶数
        {
             hangshu=iwz/n;
             hangshucha=n-1-hangshu;
             //printf("hangshucha=%d\n",hangshucha);
             panduanshu=nxs+hangshucha;
             if(panduanshu%2==0)
                   printf("YES\n");
              else 
                   printf("NO\n");      
        }                        
   } 
   return 0;    
}

c d e d e f <=> d e @ f g h f g h @ g h f

 

1 2 3 4

地方在计算机上写起来不是太清楚。

理是:

5 6 7 8

 

 

 

 

2.
先把要移到最后位置的那个数移到最后四个位置之一,然后再将空格移到最后一

 

1 2 3

由于原始状态的逆序为0(偶数),则逆序为偶数的状态有解。

l。

 

我们首先从经典的八数码问题入手,即对于八数码问题的任意一个排列是否有解?有解的条件是什么?

我们先来看看4×4的情况,同样的思路,我们考虑移动空格时逆序的变化情况。

空格的合法变化。
这个引理也是比较容易证明的。我们只要证明如下的几种状态之

 

 

 

 

是空格@和相邻的数对换,一种是空格@和前后隔两个数的数之间的对换,前者对应着空

9 A B

证完了这三个引理,定理的成立就是显然的了。首先,将奇偶性相同的两种状态都

两类,逆序奇类和逆序偶类。相对应的,九宫图(除去空格)也有它的奇偶性,我们的定

偶数对逆序,称之为逆序偶。这样,对于1,2,…,n这n个数,其所有的排列可以分为

变换到上述两种标准状态之一,然后对其一去逆变换即可。以上是我的所有证明,有些

 

 

个一个去搜索去判断哪些有解哪些误解,无疑要花费很长的时间,也没必要。作为一种

 

样,我们的每一个变换后,8还是保持在最后一个,余类似),再将7移到8之前,然后,

呢?对于有解的问题,是否能通过一种固定的步骤来得到解?经过昨天晚上和今天的仔

9 A B

三个数的轮换,我们可以自己列举一下几种情况验证一下。这就说明了奇九宫图和偶九

另外水木清华BBS论坛中有人提到:

法把8移到最后一个,然后8保持不动(注意,我们这里的不动只是形式上不动,但不管怎

考虑左右移动空格,逆序不变;同一层上下移动空格,跨过N-1个格子;上下层移动空格,跨过N^2-1个格子。

 

格在九宫图中的左右移动,后者对应着空格在九宫图中的上下移动。

>推广二维N×N的棋盘

为了方便讨论,我们把它写成一维的形式,并以0代替空格位置。那么表示如下:

当N为偶数时,N-1和N^2-1均为奇数,也就是令空格位置到目标状态空格位置的y
z方向的距离之和,称为空格距离。若空格距离为偶数,两个逆序奇偶性相同的状态可相互到达;若空格距离为奇数,两个逆序奇偶性不同的状态可相互到达。

也就是说,逆序的奇偶将所有的状态分为了两个等价类,同一个等价类中的状态都可相互到达。

宫图之间是互不可达的。

一、我的结论

其实,三维的结论和二维的结论是一样的。

 

N为偶数时,空格每上下移动一次,奇偶性改变。称空格位置所在的行到目标空格所在的行步数为空格的距离(不计左右距离),若两个状态的可相互到达,则有,两个状态的逆序奇偶性相同且空格距离为偶数,或者,逆序奇偶性不同且空格距离为奇数数。否则不能。

然而以下状态就是一个有解的状态(交换了前两个数字1 2):

2 1 3 4 5 6 7 8 0

 

我的证明分好几个步骤,恳请大家能够耐心的看下去,我会尽量说得简洁一点。

间是互达的: a b c a b @ a b c a b c @ d e <=>

若两个状态的逆序奇偶性相同,则可相互到达,否则不可相互到达。

最后,并且对变换仅限于这四个位置上。显然,对于a,c是一步就可以做到的。对于b,

ps:http://acm.hdu.edu.cn/showproblem.php?pid=3600

我在网上搜了半天,找到一个十分简洁的结论。八数码问题原始状态如下:

2 1 3 4

九宫图之间互不可达。

//题解:八数码问题,逆序数

//代码:

#include<stdio.h>

#define SIZE_N 90010

int ary[2][SIZE_N];
int sum,len;

void reverseNum(int l,int h,int idx)
{
    int i,j,k;
    int mid,idxt;

    idxt = 1 - idx;
    if(l == h) {
        ary[1][l] = ary[0][l];
        return ;
    }
    mid = (l + h) / 2;
    reverseNum(l, mid, idxt);
    reverseNum(mid+1, h, idxt);
    for(i = j = l,k = mid+1;i <= mid && k <= h;) {
        if(ary[idx][i] < ary[idx][k]) {
            ary[idxt][j++] = ary[idx][i];
            sum += k - mid - 1;
            i ++;
        }
        else {
            ary[idxt][j++] = ary[idx][k];
            k ++;
        }
    }
    for(i;i <= mid;i ++) {
        ary[idxt][j++] = ary[idx][i];
        sum += h - mid;
    }
    for(k;k <= h;k ++) {
        ary[idxt][j++] = ary[idx][k];
    }
}

int main()
{
    int n;
    int i;

    while(scanf("%d",&n),n != 0) {
        len = n * n;
        for(i = 0;i < len;i ++) {
            scanf("%d",&ary[0][i]);
            if(ary[0][i] == 0) {
                if(!(n & 1)) {
                    sum = (n - i / n - 1);
                }
                else {
                    sum = 0;
                }
                i --;
                len --;
            }
        }
        if(n == 1) {
            puts("YES");
            continue;
        }
        reverseNum(0, len-1, 0);
        if(sum & 1) {
            puts("NO");
        }
        else {
            puts("YES");
        }
    }
    return 0;
}

 

此结论只是由观察得知的,但是还没证明过,请高手指点。

另外再详细说明一下,无论N是奇数还是偶数,空格上下移动,相当于跨过N-1个格子。那么逆序的改变可能为一下值±N-1,±N-3,±N-5
……
±N-2k-1。当N为奇数数时N-1为偶数,逆序改变可能为0;当N为偶数时N-1为奇数,逆序的改变不能为0,只能是奇数,所以没上下移动一次奇偶性必然改变。

二、问题的转化

 

 

 

引理二:转化后行序列在上面定义的两种对换下的任意操作,可以转换成九宫图中

通过实验得知,以下状态是无解的(交换了前两个数字1 2):

 

步骤如下: a b c @ -> @ b c a -> b @ c a -> b c @ a -> b c a
@ -> @ c a b

细分析,我觉得我已经得到了这个问题的初步解答,下面我公布一下我得到的结果和证

4 5 6

 

为了证明上述定理,我想先对问题进行一下转化。我定义两种行序列的变换:一种

 

 

 

 

 

 

简要说明一下:当左右移动空格时,逆序不变。当上下移动空格时,相当于将一个数字向前(或向后)移动两格,跳过的这两个数字要么都比它大(小),逆序可能±2;要么一个较大一个较小,逆序不变。所以可得结论:只要是相互可达的两个状态,它们的逆序奇偶性相同。我想半天只能说明这个结论的必要性,详细的证明请参考后面的附件。

  1. 对于 a b c @ ,我们可以将其中的任意一个移到

一个状态表示成一维的形式,求出除0之外所有数字的逆序数之和,也就是每个数字前面比它大的数字的个数的和,称为这个状态的逆序。

这个状态的逆序为1,和原始状态奇偶性不同,而空格位置在第三行。由于空格每从第三行移动到第四行,奇偶性改变。则该状态的可到达原始状态。

 

,九宫格的每一种状态和上图的行之间是一一对应的。在代数上册我们学过逆序的概念

引理三:所有的奇状态可以转换为 @ 1 2 3 4 5 6 7 8, 所有的偶状态

的想法是可以实现的。如下:

 

g h 通过计算机搜索,可以发现上面两对状态之间的确是互达的。从而,我们可以

D E F

 

admin

相关文章

发表评论

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