青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

ACRUSH(樓天成)八數碼問題源代碼

題目描述
八方塊移動游戲要求從一個含8個數字(用1-8表示)的方塊以及一個空格方塊(用0表示)的3x3矩陣的起始狀態開始,不斷移動該空格方塊以使其和相鄰的方塊互換,直至達到所定義的目標狀態??崭穹綁K在中間位置時有上、下、左、右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 閱讀(18323) 評論(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  回復  更多評論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            91久久精品一区二区三区| 国产在线欧美日韩| 99视频精品免费观看| 亚洲精品免费电影| 欧美福利视频在线| 亚洲天堂网在线观看| 亚洲一区欧美激情| 国产在线高清精品| 欧美激情在线播放| 欧美日韩一区二区三区视频 | 国产一区二区三区久久悠悠色av| 久久人人爽人人| 男女激情久久| 午夜国产精品影院在线观看 | 亚洲婷婷免费| 精品成人在线观看| 99re6这里只有精品视频在线观看| 国产精品爽爽爽| 欧美成人嫩草网站| 国产精品久久久久秋霞鲁丝| 美女视频网站黄色亚洲| 欧美日韩国产免费| 久久久久**毛片大全| 欧美大秀在线观看| 久久久av水蜜桃| 欧美理论在线播放| 久久香蕉国产线看观看网| 亚洲欧洲中文日韩久久av乱码| 国产精品福利在线观看网址| 欧美成年人视频网站| 国产精品狠色婷| 欧美好吊妞视频| 国产日韩亚洲欧美| 一区二区精品在线| 亚洲精品欧美极品| 久久久xxx| 欧美在线视频日韩| 欧美日韩一视频区二区| 欧美顶级艳妇交换群宴| 国产欧美一区二区视频| aⅴ色国产欧美| 亚洲欧洲在线免费| 久久久久国产一区二区三区四区| 午夜精品久久久久久久99黑人| 欧美二区不卡| 欧美高清影院| 黄色一区二区在线| 欧美在线观看一区二区三区| 亚洲字幕在线观看| 欧美日一区二区三区在线观看国产免| 免费高清在线视频一区·| 国产拍揄自揄精品视频麻豆| 亚洲天堂成人在线视频| 亚洲尤物在线| 欧美午夜性色大片在线观看| 亚洲日韩欧美一区二区在线| 亚洲精品国产精品国自产在线| 久久久久成人网| 美乳少妇欧美精品| 尤物精品在线| 老司机免费视频久久| 欧美大片在线影院| 亚洲毛片在线| 欧美日韩国产成人在线免费| 亚洲精品一二三| 亚洲综合大片69999| 国产精品a久久久久| 亚洲视频在线观看网站| 亚洲综合视频在线| 国产精品系列在线播放| 亚洲欧美成人一区二区三区| 久久国产精品久久久久久| 国产亚洲精品久久久久婷婷瑜伽| 亚洲欧美日韩中文视频| 久久免费99精品久久久久久| 娇妻被交换粗又大又硬视频欧美| 久久久久国产精品www| 欧美黄色视屏| 亚洲一区二区三区中文字幕 | 久久天堂成人| 亚洲国产成人午夜在线一区| 亚洲视频香蕉人妖| 国产欧美日韩亚州综合| 久久天天狠狠| 亚洲精品视频中文字幕| 欧美一级理论性理论a| 极品尤物久久久av免费看| 欧美激情性爽国产精品17p| 一本久久a久久免费精品不卡| 欧美一区高清| 亚洲日本欧美天堂| 国产精品日韩一区二区| 久久综合网络一区二区| 一本一本a久久| 久久噜噜亚洲综合| 亚洲永久精品大片| 欧美国产日韩精品| 亚洲午夜av| 欧美激情在线有限公司| 亚洲曰本av电影| 亚洲国产激情| 国产欧美日韩精品专区| 欧美暴力喷水在线| 午夜免费电影一区在线观看| 亚洲国产天堂久久综合网| 欧美一区二区大片| 日韩视频一区二区三区| 国产一区二区三区自拍 | 欧美一级网站| 亚洲精品欧美激情| 毛片基地黄久久久久久天堂| 亚洲欧美在线免费| 亚洲日本成人| 狠狠色狠狠色综合日日五 | 久久国产视频网| 亚洲少妇在线| 亚洲精品在线一区二区| 欧美freesex8一10精品| 久久精品国内一区二区三区| 亚洲午夜日本在线观看| 亚洲日本一区二区三区| 亚洲盗摄视频| 精品99一区二区| 国产日韩欧美在线视频观看| 国产精品久久一级| 欧美视频一区二区三区| 欧美日本在线视频| 欧美高清免费| 欧美成人亚洲成人| 欧美 日韩 国产一区二区在线视频| 欧美一级久久久| 亚洲欧美综合一区| 午夜在线一区| 午夜久久久久久| 午夜视频在线观看一区二区三区| 国产精品99久久久久久白浆小说| 99国产精品99久久久久久| 亚洲激情成人| 亚洲精品一区在线| 亚洲美女尤物影院| 亚洲伦伦在线| 国产精品99久久久久久www| 一区二区三区精密机械公司| 一区二区免费看| 亚洲视频综合在线| 亚洲欧美日韩专区| 久久精品伊人| 噜噜噜在线观看免费视频日韩| 久久免费国产| 欧美激情视频在线免费观看 欧美视频免费一 | 欧美日韩在线一区| 国产精品家庭影院| 国产欧美一区二区精品仙草咪| 国产一区999| 亚洲国产成人av| 99在线视频精品| 亚洲一区三区电影在线观看| 欧美一区二区三区在线| 久久在线免费观看| 亚洲黄色在线看| 亚洲深夜福利视频| 久久精品一区二区三区四区| 欧美成人乱码一区二区三区| 欧美日韩精品| 国产一区二区三区视频在线观看| 亚洲第一网站| 亚洲视频在线观看网站| 久久国产乱子精品免费女| 亚洲人成毛片在线播放| 亚洲视频在线一区| 久久婷婷国产综合尤物精品| 亚洲电影激情视频网站| 亚洲色图自拍| 久久青草久久| 国产精品电影在线观看| 今天的高清视频免费播放成人| 一片黄亚洲嫩模| 久久久青草青青国产亚洲免观| 欧美激情视频给我| 亚洲欧美日本日韩| 欧美激情综合色综合啪啪| 国产亚洲一区二区三区| 日韩视频不卡| 另类天堂av| 亚洲自拍三区| 欧美精品自拍| 伊甸园精品99久久久久久| 亚洲综合社区| 亚洲国产色一区| 久久久不卡网国产精品一区| 国产精品久久久久9999高清| 亚洲国内欧美| 久久米奇亚洲| 亚洲在线播放电影| 欧美日韩成人一区二区| 亚洲电影下载| 久久综合久久综合久久综合| 亚洲一区高清| 国产精品99一区| 一本色道久久综合亚洲精品不|