hdu 1043(八數碼問題) -开发者知识库
 -开发者知识库.jpg "hdu 1043(八數碼問題) -开发者知识库,第1张")
<span style="font-family: Arial, Helvetica, sans-serif;">題意：省略</span>
解題思路：針對八數碼問題，如果x往左或往右走，是不會改變逆序數大小的，且往上或往下走只有三種情況，討論往下走，如果與x交換的數是ai，則要判斷的是a(i-1)，a(i-2)與ai的關系.
只會出現四種情況，a(i-1)>ai,a(i-2)>ai;逆序對數在原來的基礎上＋2
a(i-1)<ai,a(i-2)>ai;逆序對數在原來的基礎上不變
a(i-1)>ai,a(i-2)<ai;逆序對數在原來的基礎上不變
a(i-1)<ai,a(i-2)<ai;逆序對數在原來的基礎上－2
針對上述四種情況，逆序數的初始值為0，則經過各種變換逆序數為偶數，則若一種狀態逆序數為奇數，始不可能的。且在保存狀態時利用康托展開:X=an*(n-1)! an-1*(n-2)! ... ai*(i-1)! ... a2*1! a1*0! (ai為某個數對應的逆序對數，達到狀態壓縮)。
這里要利用反向的思維，通過最終狀態去bfs所有狀態。
只會出現四種情況，a(i-1)>ai,a(i-2)>ai;逆序對數在原來的基礎上＋2
a(i-1)<ai,a(i-2)>ai;逆序對數在原來的基礎上不變
a(i-1)>ai,a(i-2)<ai;逆序對數在原來的基礎上不變
a(i-1)<ai,a(i-2)<ai;逆序對數在原來的基礎上－2
針對上述四種情況，逆序數的初始值為0，則經過各種變換逆序數為偶數，則若一種狀態逆序數為奇數，始不可能的。且在保存狀態時利用康托展開:X=an*(n-1)! an-1*(n-2)! ... ai*(i-1)! ... a2*1! a1*0! (ai為某個數對應的逆序對數，達到狀態壓縮)。
這里要利用反向的思維，通過最終狀態去bfs所有狀態。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <queue>
using namespace std;
#define MAXN 50
#define MAZE 600000
typedef struct node{
char str[50];
int nx[9];
int num,hashnum,xind;
node();
node(char *ss,int nu,int hanu,int *nnx){
strcpy(str,ss);
num = nu;
hashnum = hanu;
for(int i=0;i<9; i){
nx[i] = nnx[i];
}
}
void charstr(){
int tmp = 0;
int tmpc;
int tmpnum = num;
tmpc = 9;
int zflag = 0;
while(num){
zflag = num;
str[tmpc -1] = '0' zflag;
if(zflag==9)
tmp = tmpc - 1;
num/=10;
--tmpc;
}
num = tmpnum;
xind = tmp;
//return tmp;
}
};
queue<node>q;
int path[MAZE];
int nx[9];
int pa[MAZE],ans[MAZE];
bool vis[MAZE];
char nows[MAXN];
int cnt;
int p[]={1,1,2,6,24,120,720,5040,40320};
int pw[] = {100000000,10000000,1000000,100000,10000,1000,100,10,1};
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int goal;
void prepro(){
cnt = 0;
int len = (int)strlen(nows);
for(int i=0;i<len; i){
if(nows[i]==32)continue;
if(nows[i]=='x')nows[i] = '9';
nows[cnt ] = nows[i];
}
nows[cnt] = 0;
}
void init(){
memset(vis,false,sizeof(vis));
memset(pa,-1,sizeof(pa));
}
int charhash(char *str){
//就保證系數ai》＝0&&ai<=(8 - i)
int ans = 0,tmpc;
int st = 0;
for(int i=0;i<cnt; i){
//if(nows[i]=='x')continue;
tmpc = 0;
for(int j = i 1;j<cnt; j){
// if(nows[j]=='x')continue;
if(str[i]>str[j])tmpc ;
}
nx[i] = tmpc;
ans =tmpc*p[8-i];
//st ;
}
return ans;
}
int getnx(){
int ans = 0;
for(int i=0;i<cnt; i){
//if(nows[i]=='x')continue;
if(nows[i]=='9')continue;
for(int j=i 1;j<cnt; j){
// if(nows[j]=='x')continue;
if(nows[i]>nows[j])
ans ;
}
}
return ans;
}
int getnumber(){
int ans = 123456789;
return ans;
}
//右 左 下 上
int gethash(char *str,int num,int dir,int xind,int nxind,node &no){
int tmpcc;
if(dir==0){
num = num-p[8-xind]*no.nx[xind] - p[8-nxind]*no.nx[nxind];
tmpcc = no.nx[nxind];
no.nx[nxind]=no.nx[xind] - 1;
no.nx[xind] = tmpcc;
num =p[8-xind]*no.nx[xind] p[8-nxind]*no.nx[nxind];
}
if(dir==1){
num = num-p[8-xind]*no.nx[xind] - p[8-nxind]*no.nx[nxind];
tmpcc = no.nx[nxind];
no.nx[nxind]=no.nx[xind] 1;
no.nx[xind] = tmpcc;
num =p[8-xind]*no.nx[xind] p[8-nxind]*no.nx[nxind];
}
if(dir==2){
int ind1,ind2;
ind1 = xind 1;
ind2 = xind 2;
int cc = 0;
if(str[nxind]>str[ind1])cc ;
if(str[nxind]>str[ind2])cc ;
num = num-p[8-xind]*no.nx[xind] - p[8-nxind]*no.nx[nxind];
tmpcc = no.nx[nxind];
no.nx[nxind]=no.nx[xind] - 3;
no.nx[xind] = tmpcc cc;
num =p[8-xind]*no.nx[xind] p[8-nxind]*no.nx[nxind];
if(str[nxind]<str[ind1]){
num-=p[8-ind1];
no.nx[ind1]--;
}
if(str[nxind]<str[ind2]){
num-=p[8-ind2];
no.nx[ind2]--;
}
}
if(dir==3){
int ind1,ind2;
ind1 = xind-1;
ind2 = xind-2;
int cc = 0;
if(str[nxind]>str[ind1])cc ;
if(str[nxind]>str[ind2])cc ;
num = num-p[8-xind]*no.nx[xind] - p[8-nxind]*no.nx[nxind];
tmpcc = no.nx[nxind];
no.nx[nxind]=no.nx[xind] 3;
no.nx[xind] = tmpcc-cc;
num =p[8-xind]*no.nx[xind] p[8-nxind]*no.nx[nxind];
if(str[nxind]<str[ind1]){
num =p[8-ind1];
no.nx[ind1] ;
}
if(str[nxind]<str[ind2]){
num =p[8-ind2];
no.nx[ind2] ;
}
}
return num;
}
//右 左 下 上
void restart(char *str,int num,int dir,int xind,int nxind,node &no){
int tmpcc;
if(dir==0){
// num = num-p[8-xind]*no.nx[xind] - p[8-nxind]*no.nx[nxind] p[8-xind]*(no.nx[nxind]-1) p[8-nxind]*no.nx[xind];
tmpcc = no.nx[xind];
no.nx[xind]=no.nx[nxind] 1;
no.nx[nxind] = tmpcc;
}
if(dir==1){
// num = num-p[8-xind]*no.nx[xind] - p[8-nxind]*no.nx[nxind] p[8-xind]*(no.nx[nxind] 1) p[8-nxind]*no.nx[xind];
tmpcc = no.nx[xind];
no.nx[xind]=no.nx[nxind] - 1;
no.nx[nxind] = tmpcc;
}
if(dir==2){
int ind1,ind2;
ind1 = xind 1;
ind2 = xind 2;
int cc = 0;
if(str[nxind]>str[ind1])cc ;
if(str[nxind]>str[ind2])cc ;
// num = num-p[8-xind]*no.nx[xind] - p[8-nxind]*no.nx[nxind] p[8-xind]*(no.nx[nxind]-2) p[8-nxind]*(no.nx[xind] cc);
tmpcc = no.nx[xind];
no.nx[xind]=no.nx[nxind] 3;
no.nx[nxind] = tmpcc-cc;
if(str[nxind]<str[ind1]){
// num =p[8-ind1];
no.nx[ind1] ;
}
if(str[nxind]<str[ind2]){
//num =p[8-ind2];
no.nx[ind2] ;
}
}
if(dir==3){
// num = num-p[8-xind]*no.nx[xind] - p[8-nxind]*no.nx[nxind] p[8-xind]*(no.nx[nxind] 2) p[8-nxind]*(no.nx[xind]-cc);
int ind1,ind2;
ind1 = xind-1;
ind2 = xind-2;
int cc = 0;
if(str[nxind]>str[ind1])cc ;
if(str[nxind]>str[ind2])cc ;
tmpcc = no.nx[xind];
no.nx[xind]=no.nx[nxind] - 3;
no.nx[nxind] = tmpcc cc;
if(str[nxind]<str[ind1]){
//num-=p[8-ind1];
no.nx[ind1]--;
}
if(str[nxind]<str[ind2]){
//num=p[8-ind2];
no.nx[ind2]--;
}
}
// return num;
}
void solve(){
//int front,rear;
// if(getnx()&1)
// return false;
int num = getnumber();
int hashnum;
hashnum = charhash("123456789");
node no("123456789",num,hashnum,nx);
no.charstr();
q.push(no);
//vis[num] = true;
int tmpnum,xind,nxind;
int x,y,nx,ny;
while(!q.empty()){
no = q.front();
q.pop();
// num = no.num;
//if(goal==no.hashnum)return true;
xind = no.xind;
if(vis[no.hashnum])continue;
vis[no.hashnum] = true;
//xind = charstr(num);
x = xind/3;
y = xind%3;
for(int i=0;i<4; i){//右 左 下 上
nx = x dx[i];
ny = y dy[i];
if(nx>=0&&nx<3&&ny>=0&&ny<3){
nxind = nx*3 ny;
tmpnum = gethash(no.str,no.hashnum,i,xind,nxind,no);
int cc = no.str[nxind] - '0';
no.str[xind] = no.str[nxind];
no.str[nxind] = '9';
// int chc = charhash(no.str);
int t1,t2;
// t1 = no.num;
t2 = no.hashnum;
if(!vis[tmpnum]){
pa[tmpnum] = no.hashnum;
path[tmpnum] = i;
// int tmpcc = num (9 - cc)*(pw[nxind]-pw[xind]);
// no.num = tmpcc;
no.hashnum = tmpnum;
no.xind = nxind;
q.push(no);
}
no.str[nxind] = no.str[xind];
no.str[xind] = '9';
// no.num = t1;
no.hashnum = t2;
no.xind = xind;
restart(no.str,no.hashnum,i,xind,nxind,no);
}
}
}
// return false;
}
int getdir(int num){
switch(num){
case 0: return 'l';
case 1: return 'r';
case 2: return 'u';
case 3: return 'd';
}
return 0;
}
void output(bool flag,int hashnum){
if(!flag){
printf("unsolvable\n");
return;
}
int cntans = 0;
int tmp = hashnum;
//char ss[]="ullddrurdllurdruldr";
//printf("%d\n",strlen(ss));
while(1){
if(pa[tmp]==-1)break;
ans[cntans ] = path[tmp];
tmp = pa[tmp];
}
//printf("%d",ans[0]);
// printf("%d\n",cntans);
for(int i=0;i<cntans; i){
putchar(getdir(ans[i]));
}
printf("\n");
}
void clear(){
while(!q.empty()){
q.pop();
}
}
int main(){
init();
goal = 0;
solve();
//clear();
bool flag;
while(gets(nows)){
flag = true;
prepro();
int hashnum = charhash(nows);
if(!vis[hashnum])flag = false;
output(flag,hashnum);
}
return 0;
}
最佳答案：
本文经用户投稿或网站收集转载，如有侵权请联系本站。
