题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4021
这个问题开始是不会的,就想当然做,只要交换8个死角的0位置,然后判断8个位置是否相等然后就决定能否转换到
想当然了,后来一直wa,看了题解才知道不是这样!
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <cmath> using namespace std; #define maxn 24 int begin[maxn],end[maxn]; int first[maxn],second[maxn],pre[maxn]; int pos[10]={0,1,2,7,16,21,22,23}; int init(){ pre[0]=pre[2]=3,pre[1]=pre[7]=6; pre[16]=pre[22]=17,pre[21]=pre[23]=20; return 0; } int main(){ int i,j,k,t,num1,num2,ans3; int ans1,ans2,pos1,pos2; init(); scanf("%d",&t); while(t--){ for(i=0;i<maxn;i++) scanf("%d",&begin[i]); for(i=0;i<maxn;i++) scanf("%d",&end[i]); for(i=0;i<maxn;i++) for(j=0;j<8;j++){ if(begin[pos[j]]==0) begin[pos[j]]^=begin[pre[pos[j]]],\ begin[pre[pos[j]]]^=begin[pos[j]],begin[pos[j]]^=begin[pre[pos[j]]]; if(end[pos[j]]==0) end[pos[j]]^=end[pre[pos[j]]],\ end[pre[pos[j]]]^=end[pos[j]],end[pos[j]]^=end[pre[pos[j]]]; } for(i=0;i<8;i++) if(begin[pos[i]]!=end[pos[i]]) break; if(i!=8){ printf("Y\n"); continue; } num1=num2=0; for(i=0;i<maxn;i++){ for(j=0;j<8;j++) if(i==pos[j]) break; if(j==8) first[num1++]=begin[i],second[num2++]=end[i]; } ans1=ans2=pos1=pos2=0; pos1=pos2=-1; for(i=0;i<16;i++){ if(first[i]==0) pos1=i; else for(j=0;j<i;j++) if(first[i]<first[j]) ans1++; } for(i=1;i<16;i++){ if(second[i]==0) pos2=i; else for(j=0;j<i;j++) if(second[i]<second[j]) ans2++; } ans3=abs(pos1/4-pos2/4); if(abs((ans1-ans2+ans3))%2==0)printf("N\n"); else printf("Y\n"); } return 0; }
下面是别人的题解总结的很好
题意:给出一个board,上面有24个位置,其中23个位置上放置了标有数字1~23的方块,一个为空位(用数字0表示),现在可以把空位与它旁边的方块交换,给出board的起始状态,问是否可以达到指定的状态。
思路:看起来很像著名的“八数码”问题,首先,针对八个特殊位置(死角),如果这里有空位就把它和相邻的位置交换,这样之后如果两个状态的对应死角上的数字不同,那么显然是不能达到指定状态的,因为无法把死角处的数字换出去。
搞定了死角后就只剩下4×4的board了,这就变成了八数码问题的拓展——15数码。首先想想八数码是如何判断有解的:首先把所有数字(不包括空位的0)写成一行,就得到了一个1~8的排列,考虑空位的交换情况:1.左右交换,2.上下交换。对于左右交换而言,是不会改变写出的排列的逆序数的;而对上下交换,相当于在排列中向前或向后跳了两个位置,那么要么两个数都比它大或小,这样逆序数加2或减2,要么两个数一个比它大一个比它小,这样逆序数不变,综上,对于八数码问题,操作不会改变逆序数的奇偶性,所以只有初始状态和指定状态的逆序数奇偶性相同就有解。
弄清楚了八数码,扩展起来就容易了,现在我们将其扩展到N维(即N*N的board,N*N-1数码问题)。
首先无论N的奇偶,左右交换不改变逆序数,N为奇数时:上下交换逆序数增加N-1或减少N-1或不变,因为N为奇数,所以逆序数奇偶性不变;而N为偶数时:上下交换一次奇偶性改变一次。
结论:N为奇数时,初始状态与指定状态逆序数奇偶性相同即有解;N为偶数时,先计算出从初始状态到指定状态,空位要移动的行数m,如果初始状态的逆序数加上m与指定状态的逆序数奇偶性相同,则有解。
好了,现在这道题就简单了,计算逆序数和空格要移动的行数即可。