ACM程序設(shè)計競賽例題

1、備戰(zhàn)ACM資料一：知識點 數(shù)據(jù)結(jié)構(gòu)： 1，單，雙鏈表及循環(huán)鏈表 2，樹的表示與存儲，二叉樹（概念，遍歷）二叉樹的 應(yīng)用（二叉排序樹，判定樹，博弈樹，解答樹等） 3，文件操作（從文本文件中讀入數(shù)據(jù)并輸出到文本文 件中） 4，圖（基本概念，存儲結(jié)構(gòu)，圖的運算） 數(shù)學(xué)知識 1，離散數(shù)學(xué)知識的應(yīng)用（如排列組合、簡單的圖論，數(shù) 理邏輯） 2，數(shù)論知識 3，線性代數(shù) 4，組合代數(shù) 5，計算幾何二 算法 1，排序算法（冒拋法，插入排序，合并排序，快速排 序，堆排序） 2，查找（順序查找，二分發(fā)） 3，回溯算法 4，遞歸算法 5，分治算法 6，模擬法 7，貪心法 8，簡單搜索算法（深度優(yōu)先，廣度優(yōu)先），搜索中

2、的 剪枝，A*算法 9，動態(tài)規(guī)劃的思想及基本算法 10，高精度運算 三、ACM競賽的題型分析 競賽的程序設(shè)計一般只有16種類型，它們分別是： Dynamic Programming （動態(tài)規(guī)劃） Greedy （貪心算法） Complete Search （窮舉搜索） Flood Fill （不知該如何翻譯） Shortest Path （最短路徑） Recursive Search Techniques （回溯搜索技術(shù)） Minimum Spanning Tree （最小生成樹） Knapsack （背包問題） Computational Geometry (計算幾何學(xué)) Network F

3、low （網(wǎng)絡(luò)流） Eulerian Path （歐拉回路） Two-Dimensional Convex Hull （不知如何翻譯） BigNums （大數(shù)問題） Heuristic Search （啟發(fā)式搜索） Approximate Search （近似搜索） Ad Hoc Problems （雜題） 四 ACM競賽參考書 實用算法的分析與程序設(shè)計 （吳文虎，王建德著，電子工業(yè)出版社，競賽類的黑寶書） 青少年國際和全國信息學(xué)（計算機）奧林匹克競賽指導(dǎo)）組合數(shù)學(xué)的算法 和程序設(shè)計（吳文虎，王建德著，清華大學(xué)出版社，參加競賽組合數(shù)學(xué)必學(xué)） 計算機算法設(shè)計與分析 （王曉東編著，最好的數(shù)據(jù)結(jié)構(gòu)教

4、材） 數(shù)據(jù)結(jié)構(gòu)與算法 （傅清祥，王曉東編著，我所見過的最好的算法教材） 信息學(xué)奧林匹克競賽指導(dǎo)1997-1998競賽試題解析（吳文虎，王建德著，清華大學(xué)出版社） 計算機程序設(shè)計技巧 D.E.Kruth著，算法書中最著名的葵花寶典，大師的作品，難度大） 計算幾何周陪德著 ACM國際大學(xué)生程序設(shè)計競賽試題與解析（一） （吳文虎著，清華大學(xué)出版社） 數(shù)學(xué)建模競賽培訓(xùn)教材 共三本 葉其孝主編 數(shù)學(xué)模型 第二版 姜啟源 隨機規(guī)劃 模糊數(shù)學(xué) 數(shù)學(xué)建模入門 徐全智 計算機算法設(shè)計與分析 國防科大 五 常見的幾個網(wǎng)上題庫 常用網(wǎng)站： 1）信息學(xué)初學(xué)者之家：/ （2

5、）大榕樹編程世界：/drs/program/default.asp （3）中國教育曙光網(wǎng)：/aosai/ （4）福建信息學(xué)奧林匹克： （5）第20屆全國青少年信息學(xué)奧林匹克競賽：/ （6）第15屆國際青少年信息學(xué)奧林匹克競賽：/ （7）全美計算機奧林匹克競賽： （8）美國信息學(xué)奧林匹克競賽官方網(wǎng)站：/ （9）俄羅斯Ural州立大學(xué)：http:/acm.timus.ru/ （10）西班牙

6、Valladolid大學(xué)：http:/acm.uva.es/problemset （11）ACM-ICPC：/icpc/ （12）北京大學(xué)： （13）浙江大學(xué)： （14）IOI：http:/olympiads.win.tue.nl/ioi/ （15）2003年江蘇省信息學(xué)奧林匹克競賽夏令營： （16） （17） （18） （19） （20） colin_fox/colin_fox 五 如何備戰(zhàn)ACM/ICPC 1，個人準備（算法書，習(xí)題集，網(wǎng)上做題和討論） 2，1000題=亞洲冠軍=世界決賽 3，做好資料收集和整理工作 實驗一：遞歸與分治1.二分查找2

7、.合并排序3.快速排序?qū)嶒灦夯厮?.0-1背包問題2.裝載問題3.堡壘問題（ZOJ1002）4.*翻硬幣問題5.8皇后問題6.素數(shù)環(huán)問題7.迷宮問題8.*農(nóng)場灌溉問題（ZOJ2412）9.*求圖像的周長（ZOJ1047）10.*骨牌矩陣11.*字母轉(zhuǎn)換（ZOJ1003）12.*踩氣球（ZOJ1004）實驗三：搜索1.Floodfill2.電子老鼠闖迷宮3.跳馬4.獨輪車5.皇宮小偷6.分酒問題7.*找倍數(shù)8.*8數(shù)碼難題實驗四：動態(tài)規(guī)劃1.最長公共子序列2.計算矩陣連乘積3.凸多邊形的最優(yōu)三角剖分4.防衛(wèi)導(dǎo)彈5.*石子合并6.*最小代價子母樹7.*旅游預(yù)算8.*皇宮看守9.*游戲室問題10.

8、*基因問題11.*田忌賽馬實驗五：貪心與隨機算法1.背包問題2.搬桌子問題3.*照亮的山景4.*用隨即算法求解8皇后問題5.素數(shù)測試實驗一：遞歸與分治實驗?zāi)康睦斫膺f歸算法的思想和遞歸程序的執(zhí)行過程，并能熟練編寫遞歸程序。掌握分治算法的思想，對給定的問題能設(shè)計出分治算法予以解決。實驗預(yù)習(xí)內(nèi)容編程實現(xiàn)講過的例題：二分搜索、合并排序、快速排序。對本實驗中的問題，設(shè)計出算法并編程實現(xiàn)。試驗內(nèi)容和步驟1二分查找在對線性表的操作中，經(jīng)常需要查找某一個元素在線性表中的位置。此問題的輸入是待查元素x和線性表L，輸出為x在L中的位置或者x不在L中的信息。程序略2合并排序程序略3快速排序程序略實驗總結(jié)及思考合并排

9、序的遞歸程序執(zhí)行的過程 實驗二：回溯算法實驗?zāi)康模菏炀氄莆栈厮菟惴▽嶒瀮?nèi)容：回溯算法的幾種形式a)用回溯算法搜索子集樹的一般模式void search(int m)if(m>n) /遞歸結(jié)束條件 output(); /相應(yīng)的處理(輸出結(jié)果)elseam=0; /設(shè)置狀態(tài)：0表示不要該物品search(m+1); /遞歸搜索：繼續(xù)確定下一個物品am=1; /設(shè)置狀態(tài)：1表示要該物品search(m+1); /遞歸搜索：繼續(xù)確定下一個物品b)用回溯算法搜索子集樹的一般模式void search(int m)if(m>n) /遞歸結(jié)束條件 output(); /相應(yīng)的處理(輸出結(jié)果)el

10、sefor(i=m;i<=n;i+)swap(m,i); /交換am和aiif()if(canplace(m) /如果m處可放置search(m+1); /搜索下一層swpa(m,i); /交換am和ai(換回來)習(xí)題10-1背包問題在0 / 1背包問題中，需對容量為c 的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高。 程序如下：#include <stdio.h>void readdata();void search(int);void c

11、heckmax();void printresult();int c=35, n=10; /c： 背包容量；n：物品數(shù)int w10, v10; /wi、vi：第i件物品的重量和價值int a10, max; /a數(shù)組存放當(dāng)前解各物品選取情況；max：記錄最大價值 /ai=0表示不選第i件物品，ai=1表示選第i件物品int main()readdata(); /讀入數(shù)據(jù)search(0); /遞歸搜索printresult();void search(int m)if(m>=n)checkmax(); /檢查當(dāng)前解是否是可行解，若是則把它的價值與max比較elseam=0; /不選第m

12、件物品search(m+1); /遞歸搜索下一件物品am=1; /不選第m件物品search(m+1); /遞歸搜索下一件物品void checkmax()int i, weight=0, value=0;for(i=0;i<n;i+)if(ai=1) /如果選取了該物品weight = weight + wi; /累加重量value = value + vi; /累加價值if(weight<=c) /若為可行解if(value>max) /且價值大于maxmax=value; /替換maxvoid readdata()int i;for(i=0;i<n;i+)scan

13、f("%d%d",&wi,&vi); /讀入第i件物品重量和價值void printresult()printf("%d",max);2裝載問題有兩艘船，載重量分別是c1、 c2，n個集裝箱，重量是wi (i=1n)，且所有集裝箱的總重量不超過c1+c2。確定是否有可能將所有集裝箱全部裝入兩艘船。提示：求出不超過c1的最大值max，若總重量max < c2則能裝入到兩艘船。3堡壘問題（ZOJ1002）如圖城堡是一個4×4的方格，為了保衛(wèi)城堡，現(xiàn)需要在某些格子里修建一些堡壘。城堡中的某些格子是墻，其余格子都是空格，堡壘只能建

14、在空格里，每個堡壘都可以向上下左右四個方向射擊，如果兩個堡壘在同一行或同一列，且中間沒有墻相隔，則兩個堡壘都會把對方打掉。問對于給定的一種狀態(tài)，最多能夠修建幾個堡壘。程序主要部分如下：int main()readdata(); /讀入數(shù)據(jù)search(0); /遞歸搜索printresult();void search(int m)int row, col;row=m/n; /求第m個格子的行號col=m%n; /求第m個格子的列號if(m>=n*n)checkmax(); /檢查當(dāng)前解是否是可行解，若是則把它的價值與max比較elsesearch(m+1); /該位置不放堡壘遞歸搜索下

15、一個位置if(canplace(m) /判斷第m個格子是否能放堡壘place(m); /在第m個格子上放置一個堡壘search(m+1); /遞歸搜索下一個位置takeout(m); /去掉第m個格子上放置的堡壘4翻硬幣問題把硬幣擺放成32×9的矩陣，你可以隨意翻轉(zhuǎn)矩陣中的某些行和某些列，問正面朝上的硬幣最多有多少枚？提示：（1）任意一行或一列，翻兩次等于沒有翻； （2）對于9列的任何一種翻轉(zhuǎn)的情況，每一行翻與不翻相互獨立。58皇后問題在一個×的棋盤里放置個皇后，要求這8個皇后兩兩之間互相都不“沖突”。#include <stdio.h>#include <

16、;math.h>void search(int);void printresult(); /打印結(jié)果int canplace(int,int); /判斷該位置能否放置皇后void place(int,int); /在該位置能否放置皇后void takeout(int,int); /把該位置放置皇后去掉int a8; /ai存放第i個皇后的位置int main()search(0); /遞歸搜索void search(int m)int i;if(m>=8) /當(dāng)已經(jīng)找出一組解時printresult(); /輸出當(dāng)前結(jié)果elsefor(i=0;i<8;i+) /對當(dāng)前行0到7

17、列的每一個位置if(canplace(m,i) /判斷第m個格子是否能放堡壘place(m,i); /在(m,i)格子上放置一個皇后search(m+1); /遞歸搜索下一行takeout(m,i); /把(m,i)格子上的皇后去掉int canplace(int row, int col)int i;for(i=0;i<row;i+)if(abs(i-row)=abs(ai-col)|ai=col)return(0);return(1);void place(int row, int col)arow=col;void takeout(int row, int col)arow=-1;

18、void printresult()int i,j;for(i=0;i<8;i+)for(j=0;j<8;j+)if(ai=j)printf(" A ");elseprintf(" . ");printf("n");printf("n");6素數(shù)環(huán)問題把從1到20這20個數(shù)擺成一個環(huán)，要求相鄰的兩個數(shù)的和是一個素數(shù)。分析：用回溯算法，考察所有可能的排列。程序如下：#include <stdio.h>#include <math.h>void search(int);void in

19、it(); /初始化void printresult(); /打印結(jié)果int isprime(int); /判斷該數(shù)是否是素數(shù)void swap(int,int); /交換am和aiint a21; /a數(shù)組存放素數(shù)環(huán)int main()init();search(2); /遞歸搜索int isprime(int num)int i,k;k=sqrt(num);for(i=2;i<=k;i+)if(num%i=0)return(0);return(1);void printresult()int i;for(i=1;i<=20;i+)printf("%3d",a

20、i);printf("n");void search(int m)int i;if(m>20) /當(dāng)已經(jīng)搜索到葉結(jié)點時if(isprime(a1+a20) /如果a1+a20也是素數(shù)printresult(); /輸出當(dāng)前解return;elsefor(i=m;i<=20;i+) /(排列樹)swap(m,i); /交換am和aiif(isprime(am-1+am) /判斷am-1+am是否是素數(shù)search(m+1); /遞歸搜索下一個位置swap(m,i); /把am和ai換回來void swap(int m, int i)int t;t=am;am=ai

21、;ai=t;void init()int i;for(i=0;i<21;i+)ai=i;7迷宮問題給一個20×20的迷宮、起點坐標和終點坐標，問從起點是否能到達終點。輸入數(shù)據(jù)：.表示空格；X表示墻。程序如下：#include <stdio.h>#include <math.h>void search(int,int);int canplace(int,int);void readdata(); /讀入數(shù)據(jù)void printresult(); /打印結(jié)果int a2020; /a數(shù)組存放迷宮int s,t;int main()int row, col;r

22、eaddata();row=s/20;col=s%20;search(row,col); /遞歸搜索printresult();void search(int row, int col)int r,c;arowcol=1;r=row; /左c=col-1;if(canplace(r,c) /判斷(r,c)位置是否已經(jīng)走過search(r,c); /遞歸搜索(r,c)r=row+1; /下c=col;if(canplace(r,c) /判斷(r,c)位置是否已經(jīng)走過search(r,c); /遞歸搜索(r,c)r=row; /右c=col+1;if(canplace(r,c) /判斷(r,c)位

23、置是否已經(jīng)走過search(r,c); /遞歸搜索(r,c)r=row-1; /上c=col;if(canplace(r,c) /判斷(r,c)位置是否已經(jīng)走過search(r,c); /遞歸搜索(r,c)void printresult()int i,j;for(i=0;i<20;i+)for(j=0;j<20;j+)printf("%3d",aij);printf("n");void readdata()int i,j;for(i=0;i<20;i+)for(j=0;j<20;j+)scanf("%d",&

24、amp;aij);int canplace(int row, int col)if(row>=0&&row<20&&col>=0&&col<20&&arowcol=0)return 1;elsereturn 0;8農(nóng)場灌溉問題（ZOJ2412）一農(nóng)場由圖所示的十一種小方塊組成，藍色線條為灌溉渠。若相鄰兩塊的灌溉渠相連則只需一口水井灌溉。給出若干由字母表示的最大不超過50×50具體由(m，n)表示，的農(nóng)場圖，編程求出最小需要打的井?dāng)?shù)。每個測例的輸出占一行。當(dāng)M=N=-1時結(jié)束程序。 Sample I

25、nput2 2DKHF3 3ADCFJKIHE-1 -1Sample Output23 提示：參考迷宮問題，實現(xiàn)時關(guān)鍵要解決好各塊的表示問題。9求圖像的周長（ZOJ1047）給一個用 . 和X表示的圖形，圖形在上、下、左、右、左上、左下、右上、右下8個方向都被看作是連通的，并且圖像中間不會出現(xiàn)空洞，求這個圖形的邊長。輸入：首先給出m、n、x、y四個正整數(shù)，下面給出m×n的圖形，x、y表示點擊的位置，全0表示結(jié)束。輸出：點擊的圖形的周長。 Sample Input2 2 2 2XXXX6 4 2 3.XXX.XXX.XXX.X.X.X.0 0 0 0 Sample output818提

26、示：參考迷宮問題，區(qū)別在于它是向8個方向填。10骨牌矩陣多米諾骨牌是一個小正方形方塊，每個骨牌都標有一個數(shù)字（06），現(xiàn)在有28組骨牌，每組兩個，各組編號為128，每組編號對應(yīng)的兩個骨牌數(shù)值如下：00 01 02 03 04 05 0611 12 13 14 15 16 2223 24 25 26 33 34 3536 44 45 46 55 56 66現(xiàn)將這28組骨牌排成一個7×8矩陣，此時只能看到每個骨牌上的數(shù)字（06），而不能知道每組的組號（如左下圖所示）。請編程序?qū)⒚拷M骨牌分辨出來（如右下圖所示）。7X8骨牌矩陣 骨牌組編號矩陣66265241 28 28 14 7 17 1

27、7 11 1113201034 10 10 14 7 2 2 21 2313246654 8 4 16 25 25 13 21 2310432112 8 4 16 15 15 13 9 951360455 12 12 22 22 5 5 26 2655402603 27 24 24 3 3 18 1 1960534203 27 6 6 20 20 18 1 19void search(int n) 查找下一個還沒放置骨牌的位置(x,y); 若沒有，則表示已經(jīng)找到一個解，輸出并且返回； 嘗試放置骨牌； 兩次嘗試都失敗，進行回溯；嘗試放置骨牌?把在(x,y)處的骨牌作為當(dāng)前骨牌組的一個骨牌；?把(

28、x+1,y)處的骨牌作為當(dāng)前骨牌組的另一個骨牌；?判斷當(dāng)前骨牌組是夠未被使用，如果未被使用則遞歸放置下一個骨牌組；?把(x,y +1)處的骨牌作為當(dāng)前骨牌組的另一個骨牌；?判斷當(dāng)前骨牌組是否未被使用，如果未被使用則遞歸放置下一個骨牌組；11字母轉(zhuǎn)換（ZOJ1003）通過棧交換字母順序。給定兩個字符串，要求所有的進棧和出棧序列（i表示進棧，o表示出棧），使得字符串2在求得的進出棧序列的操作下，變成字符串1。輸出結(jié)果需滿足字典序。例如TROT 到 TORT: i i i i o o o oi o i i o o i oSample Inputmadamadammbahamabahamalongsh

29、ortericriceSample Outputi i i i o o o i o o i i i i o o o o i o i i o i o i o i o o i i o i o i o o i o i o i i i o o i i o o o i o i i i o o o i o i o i o i o i o i i i o o o i o i o i o i o i o i o i i o i o i o o 12踩氣球（ZOJ1004）六一兒童節(jié)，小朋友們做踩氣球游戲，氣球的編號是1100，兩位小朋友各踩了一些氣球，要求他們報出自己所踩氣球的編號的乘積?，F(xiàn)在需要你編一個程序

30、來判斷他們的勝負，判斷的規(guī)則是這樣的：如果兩人都說了真話，數(shù)字大的人贏；如果兩人都說了假話，數(shù)字大的人贏；如果報小數(shù)字的人說的是真話而報大數(shù)字的人說謊，則報小數(shù)字的人贏（注意：只要所報的小數(shù)字是有可能的，即認為此人說了真話）。輸入為兩個數(shù)字，0 0表示結(jié)束；輸出為獲勝的數(shù)字。Sample Input36 6249 3430 0Sample Output6249 實驗三：搜索算法實驗?zāi)康模菏炀氄莆账阉魉惴▽嶒瀮?nèi)容：廣度優(yōu)先搜索搜索算法的一般模式：void search()closed表初始化為空;open表初始化為空;起點加入到open表;while( open表非空 )取open表中的一個結(jié)點

31、u;從open表中刪除u;u進入closed表;for( 對擴展結(jié)點u得到的每個新結(jié)點vi )if(vi是目標結(jié)點)輸出結(jié)果并返回;if vi 的狀態(tài)與closed表和open表中的結(jié)點的狀態(tài)都不相同vi進入open表;搜索算法關(guān)鍵要解決好狀態(tài)判重的問題，這樣可省略closed表，一般模式可改為：void search()open表初始化為空;起點加入到open表;while( open表非空 )取open表中的一個結(jié)點u;從open表中刪除u;for( 對擴展結(jié)點u得到的每個新結(jié)點vi )if(vi是目標結(jié)點)輸出結(jié)果并返回;If(notused(vi)vi進入open表;1.Floodfi

32、ll給一個20×20的迷宮和一個起點坐標，用廣度優(yōu)先搜索填充所有的可到達的格子。提示：參考第2題。2.電子老鼠闖迷宮如下圖12×12方格圖，找出一條自入口（2，9）到出口（11，8）的最短路徑。本題給出完整的程序和一組測試數(shù)據(jù)。狀態(tài)：老鼠所在的行、列。程序如下：#include<stdio.h>void readdata(); /讀入數(shù)據(jù)void init(); /初始化int search(); /廣搜，并在每一個可到達的每一個空格出填上最小步數(shù)int emptyopen(); /判棧是否為空：空：1；非空：0。int takeoutofopen(); /從棧

33、中取出一個元素，并把該元素從棧中刪除int canmoveto(int,int,int*,int*,int); /判能否移動到該方向，并帶回坐標(r,c)int isaim(int row, int col); /判斷該點是否是目標int used(int,int); /判斷該點是否已經(jīng)走過void addtoopen(int,int); /把該點加入到open表int a1212; /a存放迷宮，0表示空格，-2表示墻。 /廣搜時，未找到目標以前到達的空格，填上到達該點的最小步數(shù)int n; /n為迷宮邊長，注：若大于12，必須修改一些參數(shù)，如a的大小int open20,head,tail

34、,openlen=20; /open表int s,t; /起點和終點int main()int number;readdata(); /讀取數(shù)據(jù)init(); /初始化number=search(); /廣搜并返回最小步數(shù)printf("%d",number); /打印結(jié)果int search()int u, row, col, r, c, i, num;while(!emptyopen() /當(dāng)棧非空u=takeoutofopen(); /從棧中取出一個元素，并把該元素從棧中刪除row=u/n; /計算該點的坐標col=u%n;num=arowcol; /取得該點的步數(shù)f

35、or(i=0;i<4;i+)if(canmoveto(row,col,&r,&c,i) /判能否移動到該方向，并帶回坐標(r,c)if(isaim(r,c) /如果是目標結(jié)點return(num+1); /返回最小步數(shù)if(!used(r,c) /如果(r,c)還未到達過arc=num+1; /記錄該點的最小步數(shù)addtoopen(r,c); /把該點加入到open表int emptyopen()if(head=tail)return(1);elsereturn(0);int takeoutofopen()int u;if(head=tail)printf("e

36、rrer: stack is empty");return(-1);u=openhead+;head=head%openlen;return(u);int canmoveto(int row, int col, int *p, int *q, int direction)int r,c;r=row;c=col;switch(direction)case 0: c-; /左break;case 1: r+; /下break;case 2: c+; /右break;case 3: r-; /上*p=r;*q=c;if(r<0|r>=n|c<0|c>=n) /如果越

37、界返回0return(0);if(arc=0) /如果是空格返回1return(1);return(0); /其余情況返回0int isaim(int row, int col)if(row*n+col=t)return(1);elsereturn(0);int used(int row, int col)if(arowcol=0) / 0表示空格return(0);elsereturn(1);void addtoopen(int row, int col)int u;u=row*n+col;opentail+= u;tail=tail%openlen;void readdata()int i

38、,j,row,col;char str20;scanf("%d",&n);scanf("%d%d",&row,&col); /起點坐標s=row*n+col;scanf("%d%d",&row,&col); /終點坐標t=row*n+col;gets(str);for(i=0;i<n;i+)gets(str);for(j=0;j<n;j+)if(strj='.')aij=0; /0表示空格elseaij=-2; /2表示墻void init()head=0;tail=

39、1;open0=s;測試數(shù)據(jù)如下：12 10 7 1 8XXXXXXXXXXXXX.X.XXXX.X.XX.XX.X.XX.XXX.XX.X.X.XX.XXXXXXXXXXX.X.X.XX.XXX.XXXXX.X.XXXX.XXXX.X.XXXXXXXX.XXXXXXXXXXXXXXX注：測試數(shù)據(jù)可在運行時粘貼上去（點擊窗口最左上角按鈕，在菜單中選則“編輯”/“粘貼”即可）。想一想：此程序都存在哪些問題，如果openlen太小程序會不會出錯，加入代碼使程序能自動報出此類錯誤。3.跳馬給一個200×200的棋盤，問國際象棋的馬從給定的起點到給定的終點最少需要幾步。Sample Inpu

40、t 0 0 1 1 Sample output 4狀態(tài)：馬所在的行、列。程序如下：#include<stdio.h>void readdata(); /讀入數(shù)據(jù)void init(); /初始化int search(); /廣度優(yōu)先搜索int emptyopen(); /判棧是否為空：空：1；非空：0。long takeoutofopen(); /從棧中取出一個元素，并把該元素從棧中刪除int canmoveto(int,int,int*,int*,int); /判能否移動到該方向，并帶回坐標(r,c)int isaim(int row, int col); /判斷該點是否是目標i

41、nt used(int,int); /判斷該點是否已經(jīng)走過void addtoopen(int,int); /把該點加入到open表int a200200,n=200; /a存放棋盤，n為迷宮邊長long open2000,head,tail,openlen=2000; /open表1367long s,t; /起點和終點int search()long u;int row, col, r, c, i, num;while(!emptyopen() /當(dāng)棧非空u=takeoutofopen(); /從棧中取出一個元素，并把該元素從棧中刪除row=u/n; /計算該點所在的行col=u%n; /

42、計算該點所在的列num=arowcol; /取得該點的步數(shù)for(i=0;i<8;i+)if(canmoveto(row,col,&r,&c,i) /判能否移動到該方向，并帶回坐標(r,c)if(isaim(r,c) /如果是目標結(jié)點return(num+1); /返回最小步數(shù)if(!used(r,c) /如果(r,c)還未到達過arc=num+1; /記錄該點的最小步數(shù)addtoopen(r,c); /把該點加入到open表return -1;int main() /為了讓search()顯示在一頁內(nèi)和main函數(shù)換了以下 /一般的算法程序main函數(shù)寫在最上面讀起來更

43、方便int number;readdata(); /讀取數(shù)據(jù)init(); /初始化number=search(); /廣搜并返回最小步數(shù)printf("%d",number); /打印結(jié)果int emptyopen()if(head=tail)return(1);elsereturn(0);long takeoutofopen()long u;if(head=tail)printf("errer: stack is empty");return(-1);u=openhead+;head=head%openlen;return(u);int used(int row, int col)if(arowcol=0)return(0);elsereturn(1);void addtoo