【搜索】hdu4457 Klotski_2012杭州赛区E题-白红宇

【搜索】hdu4457 Klotski_2012杭州赛区E题

阅读量：5231 次

发布时间：2019-06-14

本文共 1804 字，大约阅读时间需要 6 分钟。

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

这个题目在现在看到就发现是一个赤裸裸到暴搜题，比赛时候由于最后只剩下40分钟给我，最后只写完一个最基本到广搜，赛后听说隔壁到师兄双向广搜就pass了=。=～

今天看到决定把它切掉，一开始写了一个双向广搜，TLE了。之后仔细一想对于20*20的数据，如果每个块大小都只是1*1一共10个块如果没有剪，由于状态数太多是不可能通过到。简单试验一下果然10*10就无可救药了，于是重写了一个A*+卡节点的版本，简单的用曼哈顿距离和做启发函数，每层卡了5000个节点，4900ms险险通过。。

双向广搜

1 //By Lin  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
           6 #include
          
             7 #include
           
             8 const int mm[4][2] = { 0,1,0,-1,1,0,-1,0}; 9 using namespace std; 10 typedef long long LL; 11 12 struct Point{ 13 int x,y; 14 Point(int _x=0 , int _y=0 ):x(_x),y(_y){} 15 }st[10],ed[10]; 16 struct Node{ 17 Point g[10]; 18 int step; 19 Node( Point h[] ,int x ) { 20 memcpy( g , h , sizeof(g) ); 21 step = x; 22 } 23 Node() {} 24 }tmp; 25 queue
            
              que1,que2; 26 set
             
               ha1,ha2; 27 vector
              
                data[10]; 28 int n,m,K; 29 char s[25][25]; 30 int now[25][25]; 31 32 LL hash(Point x[] ) { 33 LL ret = 0; 34 for (int i = 0; i
               
                =0 && x
                
                 =0 && y

//By Lin#include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             const int mm[4][2] = { 0,1,0,-1,1,0,-1,0};using namespace std;typedef long long LL;int n,m,K;struct Point{ int x,y; Point(int _x=0 , int _y=0 ):x(_x),y(_y){}}st[10],ed[10];struct Node{ Point g[10]; int dis; Node( Point h[]) { memcpy( g , h , sizeof(g) ); dis = 0; for (int i = 0; i
             
               ha;vector
              
                data[10];char s[25][25];int now[25][25];LL over;bool cmp( const Node &a , const Node &b ) { return a.dis < b.dis;}LL hash(Point x[] ) { LL ret = 0; for (int i = 0; i
               
                =0 && x
                
                 =0 && y
                 
                   3000 ) cnt[g] = 3000; cnt[h] = 0; for (int i = 0; i

转载于:https://www.cnblogs.com/lzqxh/archive/2012/11/20/2778246.html

你可能感兴趣的文章