首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

HDU 4021 24 Puzzle(11年下海 15数码)

2012-09-16 
HDU 4021 24 Puzzle(11年上海 15数码)转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/detai

HDU 4021 24 Puzzle(11年上海 15数码)

转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526       by---cxlove

题目:给出24个格子的数码的初始态和目标态,然后问能不能转换

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

思路:看起来很像著名的“八数码”问题,首先,针对八个特殊位置(死角),如果这里有空位就把它和相邻的位置交换,这样之后如果两个状态的对应死角上的数字不同,那么显然是不能达到指定状态的,因为无法把死角处的数字换出去。

搞定了死角后就只剩下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与指定状态的逆序数奇偶性相同,则有解。

好了,现在这道题就简单了,计算逆序数和空格要移动的行数即可。

#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<algorithm>#include<set>#define inf 110000000#define M 10005#define N 10005#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define pb(a) push_back(a)#define mem(a,b) memset(a,b,sizeof(a))#define LL long long#define MOD 1000000007using namespace std;int init[24],goal[24];int a[8]={0,1,2,7,16,21,22,23};int b[16]={3,4,5,6,8,9,10,11,12,13,14,15,17,18,19,20};int gao(int b){    if(b==0||b==2) return 3;    if(b==1||b==7) return 6;    if(b==16||b==22) return 17;    else return 20;}int main(){    int t;    scanf("%d",&t);    while(t--){        for(int i=0;i<24;i++)            scanf("%d",&init[i]);        for(int i=0;i<8;i++)            if(init[a[i]]==0)                swap(init[a[i]],init[gao(a[i])]);        for(int i=0;i<24;i++)            scanf("%d",&goal[i]);        for(int i=0;i<8;i++)            if(goal[a[i]]==0)                swap(goal[a[i]],goal[gao(a[i])]);        bool ans=true;        for(int i=0;i<8&&ans;i++){        //    cout<<init[a[i]]<<" "<<goal[a[i]]<<endl;            if(init[a[i]]!=goal[a[i]])                ans=false;        }        if(!ans){puts("Y");continue;}        int cnt1=0,cnt2=0,pos1=0,pos2=0;        for(int i=1;i<16;i++){            if(init[b[i]]==0){pos1=i;continue;}            for(int j=0;j<i;j++)                if(init[b[j]]>init[b[i]])                   cnt1++;        }        for(int i=1;i<16;i++){            if(goal[b[i]]==0){pos2=i;continue;}            for(int j=0;j<i;j++)                if(goal[b[j]]>goal[b[i]])                   cnt2++;        }        if((abs(pos1/4-pos2/4)+cnt1-cnt2)%2==0) puts("N");        else puts("Y");    }    return 0;}


热点排行