The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

ACRUSH(楼天成)八数码问题源代码

题目描述
八方块移动游戏要求从一个含8个数字(用1-8表示)的方块以及一个空格方块(用0表示)的3x3矩阵的起始状态开始,不断移动该空格方块以使其和相邻的方块互换,直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动,在四个角落上有2个方向可移动,在其他位置上有3个方向可移动。例如,假设一个3x3矩阵的初始状态为:
   8 0 3
   2 1 4
   7 6 5
目标状态为:
   1 2 3
   8 0 4
   7 6 5
则一个合法的移动路径为:
   8 0 3    8 1 3    8 1 3    0 1 3    1 0 3    1 2 3
   2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4
   7 6 5    7 6 5    7 6 5    7 6 5    7 6 5    7 6 5

另外,在所有可能的从初始状态到目标状态的移动路径中,步数最少的路径被称为最短路径;在上面的例子中,最短路径为5。如果不存在从初试状态到目标状态的任何路径,则称该组状态无解。

请设计有效的(细节请见评分规则)算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径,并用C/C++实现。

输入数据
程序需读入已被命名为start.txt的初始状态和已被命名为goal.txt的目标状态,这两个文件都由9个数字组成(0表示空格,1-8表示8个数字方块),每行3个数字,数字之间用空格隔开。

输出数据
如果输入数据有解,输出一个表示最短路径的非负的整数;如果输入数据无解,输出-1。

自测用例
如果输入为:start.txtgoal.txt,则产生的输出应为:
5

又例,如果用
7 8 4
3 5 6
1 0 2
替换start.txt中的内容,则产生的输出应为:
21

评分规则
1)我们将首先使用和自测用例不同的10个start.txt以及相同的goal.txt,每个测试用例的运行时间在一台Intel Xeon 2.80GHz 4 CPU/6G 内存的Linux机器上应不超过10秒(内存使用不限制),否则该用例不得分;

2)每个选手的总分(精确到小数点后6位)=10秒钟内能产生正确结果的测试用例数量x10+(1/产生这些正确结果的测试用例的平均运行毫秒);

3)如果按此评分统计仍不能得出总决赛将决出的一、二、三等奖共计九名获奖者,我们将先设N=2,然后重复下述过程直至产生最高的9位得分:用随机生成的另外10个有解的start.txt再做测试,并对这10*N个测试用例用2)中公式重新计算总分,N++。



//冠军ACRush的代码: 
//转载自:http://star.baidu.com/data/demo/ACRush.txt 

#include 
<stdio.h> 
#include 
<stdlib.h> 
#include 
<string.h> 

const int hashsize=70001
const int maxnode=50000
const int maxp=40
const int ten[]={1,10,100,1000,10000,100000,1000000,10000000,100000000}
const int C[]={2,3,2,3,4,3,2,3,2}
const int EP[][4]={{1,3,0,0},{0,2,4,0},{1,5,0,0},{0,4,6,0},{1,3,5,7},{2,4,8,0},{3,7,0,0},{4,6,8,0},{5,7,0,0}}

struct Tlist 

  
int data,d; 
  Tlist 
*next; 
}

struct Thashpoint 

  
int data; 
  Thashpoint 
*next; 
}

//Memory 
int ID; 
Tlist listM[maxnode],
*q; 
Thashpoint hashM[maxnode],
*p; 
//data 
int src,dest; 
//heap 
Tlist *head[maxp],*expand[maxp],*lp1,*lp2; 
//Hash 
Thashpoint *hash[hashsize]; 
//expand 
int nowp,A[9],arcT[9],dist[9][9],b,depth,swap[9][9]; 
int data,G,newdata,newG; 
bool find_answer; 

void readdata(const char *filename,int &data) 

  
int i,v; 
  FILE 
*f=fopen(filename,"r"); 
  data
=0
  
for (i=0;i<9;i++
  

    fscanf(f,
"%d",&v); 
    data
=data+v*ten[i]; 
  }
 
  fclose(f); 
}
 
bool check_noanswer() 

  
int p[9],i,b1,b2; 
  
bool vis[9]; 
  
for (i=0;i<9;i++
    p[i]
=arcT[src/ten[i]%10]; 
  
for (b1=0; src/ten[b1]%10!=0;b1++); 
  
for (b2=0;dest/ten[b2]%10!=0;b2++); 
  
int countP=0
  memset(vis,
false,sizeof(vis)); 
  
for (i=0;i<9;i++
    
if (!vis[i]) 
    

      countP
++
      
for (int k=i;!vis[k];k=p[k]) 
        vis[k]
=true
    }
 
  
return (countP-dist[b1][b2])%2==0
}
 
void preprocess() 

  ID
=0
  find_answer
=false
  memset(hash,
0,sizeof(hash)); 
  memset(head,
0,sizeof(head)); 
  memset(expand,
0,sizeof(expand)); 
  
for (int k=0;k<9;k++
    arcT[dest
/ten[k]%10]=k; 
  
for (int u=0;u<9;u++
    
for (int v=0;v<9;v++
    

      dist[u][v]
=abs(u/3-v/3)+abs(u%3-v%3); 
      swap[u][v]
=ten[u]-ten[v]; 
    }
 
}
 
void addnode() 

  
if (newdata==dest) 
  

    printf(
"%d\n",depth); 
    find_answer
=true
    
return
  }
 
  
int address=newdata%hashsize; 
  
for (p=hash[address];p!=NULL;p=p->next) 
    
if (p->data==newdata) 
      
return
  
if (ID==maxnode) 
    
return
  p
=&hashM[ID]; 
  p
->data=newdata; 
  p
->next=hash[address]; 
  hash[address]
=p; 
  q
=&listM[ID]; 
  ID
++
  q
->data=newdata; 
  q
->d=depth; 
  
if (newG>=maxp) 
    
return
  
if (newG==nowp) 
  

    q
->next=expand[depth]; 
    expand[depth]
=q; 
  }
 
  
else 
  

    q
->next=head[newG]; 
    head[newG]
=q; 
  }
 
}
 
void solve() 

  nowp
=-1
  newdata
=src; 
  newG
=0
  
for (int k=0;k<9;k++
    
if (src/ten[k]%10!=0
      newG
+=dist[arcT[src/ten[k]%10]][k]; 
  depth
=0
  addnode(); 
  
if (find_answer) 
    
return
  
for (int p=0;p<maxp;p++if (head[p]!=NULL) 
  

    nowp
=p; 
    
for (lp1=head[p];lp1!=NULL;lp1=lp2) 
    

      lp2
=lp1->next; 
      lp1
->next=expand[lp1->d]; 
      expand[lp1
->d]=lp1; 
    }
 
    
for (int d=0;d<=p;d++
      
for (;expand[d]!=NULL;) 
      

        data
=expand[d]->data; 
        G
=p-expand[d]->d; 
        depth
=expand[d]->d+1
        expand[d]
->d=-2
        expand[d]
=expand[d]->next; 
        
for (b=0;data/ten[b]%10!=0;b++); 
        
for (int v=0;v<C[b];v++
        

          
int u=EP[b][v]; 
          
int c=data/ten[u]%10
          newdata
=data+swap[b][u]*c; 
          c
=arcT[c]; 
          newG
=depth+G-dist[c][u]+dist[c][b]; 
          addnode(); 
          
if (find_answer) 
            
return
        }
 
      }
 
  }
 
  printf(
"-1\n"); 
}
 
int main() 

  readdata(
"start.txt",src); 
  readdata(
"goal.txt",dest); 
  preprocess(); 
  
if (check_noanswer()) 
    printf(
"-1\n"); 
  
else 
    solve(); 
  
return 0
}
 

posted on 2009-05-22 02:24 abilitytao 阅读(18112) 评论(6)  编辑 收藏 引用

评论

# re: ACRUSH(楼天成)八数码问题源代码 2009-11-22 19:56 张甡华

八数码问题存在没解的可能性吗?(排除目标不是初始状态的一个排列的情况)

qq:46522649  回复  更多评论   

# re: ACRUSH(楼天成)八数码问题源代码 2010-12-10 12:47 zlly

orz abilitytao   回复  更多评论   

# re: ACRUSH(楼天成)八数码问题源代码 2011-09-28 22:23 夜痕

@张甡华
应该是存在的  回复  更多评论   

# re: ACRUSH(楼天成)八数码问题源代码 2015-04-07 22:09 cai ji

我严重怀疑楼天城违反比赛规则,依我看楼天城用的是c的代码 却用的是c++的编译器
c里面不可能struct 这么定义这么实用的。必须有struct符号,而且看他的代码很多处还实用引用这个c里面没有的概念  回复  更多评论   

# re: ACRUSH(楼天成)八数码问题源代码[未登录] 2015-07-18 14:19 123

@cai ji
你逗呀,特么的都说了可以用c/c++。。。  回复  更多评论   

# re: ACRUSH(楼天成)八数码问题源代码 2015-10-20 16:54 dgsdg 1

gadrgadfg  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理