數(shù)據(jù)結構2-隊列及其應用課件

隊列及其應用隊列及其應用1隊列所謂隊列,就是允許在一端進行插入,在另一端進行刪除的線性表。允許插入的一端稱為隊尾。隊列是一種先進先出(FIFO)的線性表隊列的順序存儲結構和鏈式存儲結構隊列必須構造成循環(huán)隊列的形式,否則會出現(xiàn)“假溢出”#definemaxsize隊列最大容量；structline{inta[maxsize-1];intrear,front;//front隊頭;rear隊尾}隊列所謂隊列,就是允許在一端進行插入,在另一端進行刪除的線性2隊列操作舉例食堂排隊排隊買票吸管里的飲料作用：維持順序數(shù)組實現(xiàn)：元素a[0..maxn-1]，隊首front，隊尾rear入隊：rear++;a[rear]=x;出隊：ele=a[front];front++;隊空條件：front>rear問題：出隊的元素還在數(shù)組里，不是很浪費嗎？循環(huán)隊列把隊列看成環(huán)行的，則入隊：rear=(rear+1)%maxn;不定義為a[1..maxn]的原因出隊：front=(front+1)%maxn;可能存在隊滿的情況：條件也是front>rear隊列操作舉例3用隊列實現(xiàn)圖的寬度優(yōu)先搜索算法我們要對圖進行分層次遍歷,遍歷的序列為1，2，…，7，…寬度優(yōu)先搜索算法遍歷序列圖用隊列實現(xiàn)圖的寬度優(yōu)先搜索算法我們要對圖進行分層次遍歷,遍4分析要對圖進行按層次遍歷，我們可采用逐層標號法進行。方法如下：第一步：將初始點放入隊列，并將該點設置為已標號的點。第二步：從隊列中取出已標號而未檢查的點，訪問該點的所有鄰接頂點，放入隊列，并進行標號，該頂點為已檢查的點。第三步：檢查隊列中是否還有未標號的點，若有，轉第二步，否則，圖便歷完畢，算法終止。分析要對圖進行按層次遍歷，我們可采用逐層標號法進行。方法如5voidbfs(v);//從v開始寬度有先遍歷圖{inicycque(q);//初始化隊列qq.encycque(v);visted[v]:=true;//初始點v放入隊列,并標號while(!q.empty)//直到隊列不為空while(v的鄰接頂點存在){q.encycque(v的鄰接頂點);visted[v的鄰接頂點]:=true;}q.dlcycque(v);}voidbfs(v);//從v開始寬度有先遍歷圖6①已知隊列(13,2,11,34,41,77,5,7,18,26,15),第一個進入隊列的元素是13,則第五個出隊列的元素是(

)。(NOIP9)

A)5

B)41

C)77

D)13

E)18②設棧S和隊列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即進入隊列Q,若出隊的順序為e2,e4,e3,e6,e5,e1,則棧S的容量至少應該為()。(NOIP8)A)2B)3C)4D)5隊列練習試題①已知隊列(13,2,11,34,41,77,5,7,18,7【培訓試題】細胞統(tǒng)計1611Description：一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細胞,細胞的定義為沿細胞數(shù)字上下左右還是細胞數(shù)字則為同一細胞,求給定矩形陣列的細胞個數(shù)。Input：第一行為整數(shù)m,n(m<=100,n<=100分別表示m行和n列)，以下為一個mxn的矩陣Output：細胞的個數(shù)0234500067

1034560500

2045600671

0000000089【培訓試題】細胞統(tǒng)計1611Description：一矩形陣8算法步驟：1、讀入m*n矩陣,將其轉換為0、1矩陣存入pic數(shù)組中；2、沿pic數(shù)組矩陣從上到下,從左到右,找到遇到的第一個細胞；將細胞的位置入隊h,并沿其上、下、左、右四個方向搜索,如果遇到細胞(pic[i][j]=1)則將其位置入隊,入隊后的位置pic[i][j]數(shù)組置為0；3、將h隊的隊頭出隊,沿其上、下、左、右四個方向上搜索,如果遇到細胞則將其位置入隊,入隊后的位置pic數(shù)組置為0；4、重復3,直至h隊空為止,則此時找出了一個細胞；5、重復2,直至矩陣找不到細胞；6、輸出找到的細胞數(shù)。算法步驟：9voidwork(intx,inty){intfirst,last,i,h,ll;first=1;last=1;total++;hang[1]=x;lie[1]=y;while(first<last){for(i=0;i<4;i++){h=hang[first]+dx[i];ll=lie[first]+dy[i];

if(h>0&&h<=m&&ll>0&&ll<=n&&a[h][ll]){last++;hang[last]=h;lie[last]=ll;//入隊a[h][ll]=false;}}

first++;//出隊}}intmain(){init();for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(a[i][j])work(i,j);cout<<total<<endl;}voidwork(intx,inty)10【培訓試題】走迷宮2349Description有一個m*n格的迷宮(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件讀入這m*n個數(shù)據(jù)和起始點、結束點(起始點和結束點都是用兩個數(shù)據(jù)來描述的，分別表示這個點的行號和列號)?，F(xiàn)在要你編程找出所有可行的道路，要求所走的路中沒有重復的點，走時只能是上下左右四個方向。如果一條路都不可行，則輸出相應信息(用-l表示無路)。Input第一行是兩個數(shù)m，n，接下來是m行n列由1和0組成的數(shù)據(jù)，最后兩行是起始點和結束點(m,n>1且m,n<15)。Output輸出所有可能路路徑條數(shù)，如果沒有一條可行的路則輸出０。SampleInput561001011111110011101111101110111156SampleOutput：12

【培訓試題】走迷宮2349Description11【模擬試題】最少步數(shù)1800【問題描述】：在各種棋中，棋子的走法總是一定的，如中國象棋中馬走“日”。有一位小學生就想如果馬能有兩種走法將增加其趣味性，因此，他規(guī)定馬既能按“日”走，也能如象一樣走“田”字。他的同桌平時喜歡下圍棋，知道這件事后覺得很有趣，就想試一試，在一個（100*100）的圍棋盤上任選兩點A、B，A點放上黑子，B點放上白子，代表兩匹馬。棋子可以按“日”字走，也可以按“田”字走，倆人一個走黑馬，一個走白馬。誰用最少的步數(shù)走到左上角坐標為(1,1)的點時，誰獲勝?，F(xiàn)在他請你幫忙，給你A、B兩點的坐標，想知道兩個位置到（1,1）點的可能最少步數(shù)。輸入：12161810輸出：8

9【模擬試題】最少步數(shù)1800【問題描述】：在各種棋中，棋子的121、確定出發(fā)點從（x,y）出發(fā)通過一次廣度優(yōu)先搜索，可以找到從(x,y)至棋盤上所有可達點的最少步數(shù)。而問題中要求的是黑馬所在的（x1，y1）和白馬所在（x2，y2）到達(1,1)目標點的最少步數(shù)。雖然兩條路徑的起點不一樣，但是它們的終點卻是一樣的。如果我們將終點(1,1)作為起點，這樣只需要一次廣度優(yōu)先搜索便可以得到（x1，y1）和（x2，y2）到達(1,1)的最少步數(shù)。2、數(shù)據(jù)結構設queue—隊列，存儲從(1,1)可達的點（queue[k][1..2]）以及到達該點所需要的最少步數(shù)（queue[k][3]）（0≤k≤192+1）。隊列的首指針為open，尾指針為closed。初始時，queue中只有一個元素為(1,1)，最少步數(shù)為0。S—記錄(1,1)到每點所需要的最少步數(shù)。顯然，問題的答案是s[x1][y2]和s[x2][y2]。初始時，s[1][1]為0，除此之外的所有元素值設為-1。1、確定出發(fā)點13dx、dy—移動后的位置增量數(shù)組。馬有12種不同的擴展方向：馬走“日”：(x-2,y-1)(x-1,y-2)(x-2,y+1)(x-1,y+2)(x+2,y-1)(x+1,y-2)(x+2,y+1)(x+1,y+2)馬走“田”：(x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2)我們將i方向上的位置增量存入常量數(shù)組dx[i]、dy[i]中（1≤i≤12）intdx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};3、約束條件⑴不能越出界外。由于馬的所有可能的落腳點s均在s的范圍內(nèi)，因此一旦馬越出界外，就將其s值賦為0，表示“已經(jīng)擴展過，且(1,1)到達其最少需要0步”。這看上去是荒謬的，但可以簡單而有效地避免馬再次落入這些界外點。⑵該點在以前的擴展中沒有到達過。如果曾經(jīng)到達過，則根據(jù)廣度優(yōu)先搜索的原理，先前到達該點所需的步數(shù)一定小于當前步數(shù)，因此完全沒有必要再擴展下去。由此得出，馬的跳后位置（x,y）是否可以入隊的約束條件是s[x][y]<0dx、dy—移動后的位置增量數(shù)組。馬有12種不同14海上葬禮有一片被大海包圍的群島，島上居住著一個食人部族。很多年前部落里有一位巫師接受了神的召喚跳入海中，從此，那一片海域就被打上了神的烙印，被這片海域所包圍的陸地也被賦予了神圣的意義（包圍關系滿足傳遞性，即海域A包圍了島B，島B包圍了海域C，而海域C中包含了島D，則我們說海域A也包含了島D）。從那以后，部落里的巫師死后都必須葬在這片神圣海域所包圍的島上，而且每一個島都只能埋葬一位巫師（否則就會被視為對神的不敬，從而給部族帶來災難）?，F(xiàn)在給你群島的地圖和最初那位巫師跳海的地方，請你計算一下最多可以埋葬多少巫師。海上葬禮有一片被大海包圍的群島，島上居住著一個食人部族。很15地圖是一個n*m的字符矩陣，’#’代表陸地，’.’代表海洋。連通的一片陸地為一個島，連通的一片海洋為一個海域。其中，陸地從上、下、左、右4個方向連通，海洋從上、下、左、右、左上、左下、右上、右下8個方向連通。如下圖。圖3中有4個島，2片海域。如果在A處落水，則落水的海域包圍了除右上、左下兩個頂角外的3個島嶼；如果在B處落水，則只包含了中間的2個島。數(shù)據(jù)范圍是n,m<=500。地圖是一個n*m的字符矩陣，’#’代表陸地，’.’代表海洋。16分析這道題目的思路比較簡單。根據(jù)題意,可分三個步驟處理問題：做一遍floodfill,將最初的巫師落水的海域設立標記,假設為S再做一遍floodfill，將S區(qū)域所包圍的所有區(qū)域（包括海洋和陸地）設立標記，假設為E。在E區(qū)域中做一遍floodfill，統(tǒng)計有多少塊連通的陸地（即島的個數(shù)）現(xiàn)在的問題就是，用什么樣的算法實現(xiàn)floodfill。我們很容易想到深度優(yōu)先遍歷(DFS)的遞歸算法。由于要用遞歸，使用系統(tǒng)堆棧，因此對于500*500個結點的最壞情況下，會造成堆棧溢出，而且所需空間>1000kb，無法滿足題設的空間限制。在這種情況下，我們考慮深度優(yōu)先遍歷的非遞歸過程。分析這道題目的思路比較簡單。根據(jù)題意,可分三個步驟處理問17分析首先給8個方向矢量定一個序號，用一個常量數(shù)組進行記錄： CONSTd:array[1..8,1..2]ofshortint =((-1,-1),(0,-1),(-1,1),(0,1),(1,1),(0,1),(1,-1),(0,-1));建立一個順序棧S，棧的每個元素代表深度優(yōu)先遍歷路徑中的一個結點位置，記錄該位置當前擴展到的方向矢量的序號，再用一對變量Current_x，Current_y記錄棧頂元素所代表的具體位置，就可以以非遞歸的方式完成深度優(yōu)先遍歷了。分析首先給8個方向矢量定一個序號，用一個常量數(shù)組進行記錄：18PROCDfs(startX,startY:integer);初始化棧Current_xstartXCurrent_ystartYtop1;s[top]0;{初始結點入棧}標記(Current_x,Current_y)為已擴展結點whiletop>0do【s[top]st[top]+1if（s[top]<=8）and（按s[top]方向擴展的結點屬于海洋區(qū)域）and（之前沒有擴展過）then【Current_xCurrent_x+d[s[top],1]Current_yCurrent_y+d[s[top],2]標記(Current_x,Current_y)為已擴展結點toptop+1;s[top]0{新結點入棧}】else【toptop-1{當前結點退棧}iftop>0then【Current_xCurrent_x–d[s[top],1]Current_yCurrent_y–d[s[top],2]】】】ENDP

PROCDfs(startX,startY:inte19【培訓試題】最大子序和問題描述輸入一個長度為ｎ的整數(shù)序列（A1,A2,……,An），從中找出一段連續(xù)的長度不超過M的子序列，使得這個序列的和最大。【培訓試題】最大子序和問題描述20最大子序和例如：

序列1，-3，5，1，-2，3當M=2或3時S=5+1=6當M=4時S=5+1+(-2)+3=7數(shù)據(jù)范圍:50%的數(shù)據(jù)N,M<=1000100%的數(shù)據(jù)N,M<=20000最大子序和例如：當M=2或3時S=5+1=6當M=4時S=521一個簡化的問題[序列的最大連續(xù)和]輸入一個長度為ｎ的整數(shù)序列（A1,A2,……,An），從中找出一段連續(xù)的子序列，使得這個序列的和最大。和原問題相比沒有M這個序列長度的限制！一個簡化的問題[序列的最大連續(xù)和]和原問題相比沒22分析：

設F(i)表示以第i個數(shù)結尾的最大連續(xù)和以第i個數(shù)結尾的最大連續(xù)和序列，可能存在兩種選擇：情形一：只包含Ai情形二：包含Ai和以Ai-1結尾的最大連續(xù)和序列動態(tài)規(guī)劃：轉移方程：F(i)=max{Ai,F(i-1)+Ai}邊界：F(1)=A1要求的結果為max{F(i)|1<=i<=n}該算法的時間復雜度為O(n)一個簡化的問題分析：設F(i)表示以第i個數(shù)結尾的最大連續(xù)和23枚舉算法設

F(i)為以Ai結尾長度不超過M的最大子序和對于每個F(i)，從1到m枚舉k的值，完成Aj的累加和取最大值。該算法的時間復雜度為O(n2)問題初步分析枚舉算法設對于每個F(i)，從1到m枚舉k的值24簡化方程簡化方程25隊列優(yōu)化在算法中，考慮用隊列來維護決策值S(i-k)。每次只需要在隊首刪掉S(i-m-1)，在隊尾添加S(i-1)。但是取最小值操作還是需要O(n)時間復雜度的掃描。考察在添加S(i-1)的時候，設現(xiàn)在隊尾的元素是S(k)，由于k<i-1，所以S(k)必然比S(i-1)先出隊。若此時S(i-1)<=S(k)，則S(k)這個決策永遠不會在以后用到，可以將S(k)從隊尾刪除掉（此時隊列的尾部形成了一個類似棧的結構）隊列優(yōu)化在算法中，考慮用隊列來維護決策值S(i26隊列優(yōu)化同理，若隊列中兩個元素S(i)和S(j)，若i<j且S(i)>=S(j)，則我們可以刪掉S(i)（因為S(i)永遠不會被用到）。此時的隊列中的元素構成了一個單調(diào)遞增的序列，即：S1<S2<S3<……<Sk隊列優(yōu)化同理，若隊列中兩個元素S(i)和S(27我們來整理在求F(i)的時候，用隊列維護S(i-k)所需要的操作：☆若當前隊首元素S(x)，有x<i-m，則S(x)出隊；直到隊首元素S(x)有x>=i-m為止?！钊舢斍瓣犖苍豐(k)>=S(i-1)，則S(k)出隊；直到S(k)<S(i-1)為止?！钤陉犖膊迦隨(i-1)☆取出隊列中的最小值，即隊首元素。我們來整理在求F(i)的時候，用隊列維護S(i28由于對于求每個F(i)的時候，進隊和出隊的元素不止一個。但是我們可以通過分攤分析得知，每一個元素S(i)只進隊一次、出隊一次，所以隊列維護的時間復雜度是O(n)。而每次求F(i)的時候取最小值操作的復雜度是O(1)，所以這一步的總復雜度也是O(n)。綜上所述，該算法的總復雜度是O(n)由于對于求每個F(i)的時候，進隊和出隊的元素29隊列及其應用隊列及其應用30隊列所謂隊列,就是允許在一端進行插入,在另一端進行刪除的線性表。允許插入的一端稱為隊尾。隊列是一種先進先出(FIFO)的線性表隊列的順序存儲結構和鏈式存儲結構隊列必須構造成循環(huán)隊列的形式,否則會出現(xiàn)“假溢出”#definemaxsize隊列最大容量；structline{inta[maxsize-1];intrear,front;//front隊頭;rear隊尾}隊列所謂隊列,就是允許在一端進行插入,在另一端進行刪除的線性31隊列操作舉例食堂排隊排隊買票吸管里的飲料作用：維持順序數(shù)組實現(xiàn)：元素a[0..maxn-1]，隊首front，隊尾rear入隊：rear++;a[rear]=x;出隊：ele=a[front];front++;隊空條件：front>rear問題：出隊的元素還在數(shù)組里，不是很浪費嗎？循環(huán)隊列把隊列看成環(huán)行的，則入隊：rear=(rear+1)%maxn;不定義為a[1..maxn]的原因出隊：front=(front+1)%maxn;可能存在隊滿的情況：條件也是front>rear隊列操作舉例32用隊列實現(xiàn)圖的寬度優(yōu)先搜索算法我們要對圖進行分層次遍歷,遍歷的序列為1，2，…，7，…寬度優(yōu)先搜索算法遍歷序列圖用隊列實現(xiàn)圖的寬度優(yōu)先搜索算法我們要對圖進行分層次遍歷,遍33分析要對圖進行按層次遍歷，我們可采用逐層標號法進行。方法如下：第一步：將初始點放入隊列，并將該點設置為已標號的點。第二步：從隊列中取出已標號而未檢查的點，訪問該點的所有鄰接頂點，放入隊列，并進行標號，該頂點為已檢查的點。第三步：檢查隊列中是否還有未標號的點，若有，轉第二步，否則，圖便歷完畢，算法終止。分析要對圖進行按層次遍歷，我們可采用逐層標號法進行。方法如34voidbfs(v);//從v開始寬度有先遍歷圖{inicycque(q);//初始化隊列qq.encycque(v);visted[v]:=true;//初始點v放入隊列,并標號while(!q.empty)//直到隊列不為空while(v的鄰接頂點存在){q.encycque(v的鄰接頂點);visted[v的鄰接頂點]:=true;}q.dlcycque(v);}voidbfs(v);//從v開始寬度有先遍歷圖35①已知隊列(13,2,11,34,41,77,5,7,18,26,15),第一個進入隊列的元素是13,則第五個出隊列的元素是(

)。(NOIP9)

A)5

B)41

C)77

D)13

E)18②設棧S和隊列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即進入隊列Q,若出隊的順序為e2,e4,e3,e6,e5,e1,則棧S的容量至少應該為()。(NOIP8)A)2B)3C)4D)5隊列練習試題①已知隊列(13,2,11,34,41,77,5,7,18,36【培訓試題】細胞統(tǒng)計1611Description：一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細胞,細胞的定義為沿細胞數(shù)字上下左右還是細胞數(shù)字則為同一細胞,求給定矩形陣列的細胞個數(shù)。Input：第一行為整數(shù)m,n(m<=100,n<=100分別表示m行和n列)，以下為一個mxn的矩陣Output：細胞的個數(shù)0234500067

1034560500

2045600671

0000000089【培訓試題】細胞統(tǒng)計1611Description：一矩形陣37算法步驟：1、讀入m*n矩陣,將其轉換為0、1矩陣存入pic數(shù)組中；2、沿pic數(shù)組矩陣從上到下,從左到右,找到遇到的第一個細胞；將細胞的位置入隊h,并沿其上、下、左、右四個方向搜索,如果遇到細胞(pic[i][j]=1)則將其位置入隊,入隊后的位置pic[i][j]數(shù)組置為0；3、將h隊的隊頭出隊,沿其上、下、左、右四個方向上搜索,如果遇到細胞則將其位置入隊,入隊后的位置pic數(shù)組置為0；4、重復3,直至h隊空為止,則此時找出了一個細胞；5、重復2,直至矩陣找不到細胞；6、輸出找到的細胞數(shù)。算法步驟：38voidwork(intx,inty){intfirst,last,i,h,ll;first=1;last=1;total++;hang[1]=x;lie[1]=y;while(first<last){for(i=0;i<4;i++){h=hang[first]+dx[i];ll=lie[first]+dy[i];

if(h>0&&h<=m&&ll>0&&ll<=n&&a[h][ll]){last++;hang[last]=h;lie[last]=ll;//入隊a[h][ll]=false;}}

first++;//出隊}}intmain(){init();for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(a[i][j])work(i,j);cout<<total<<endl;}voidwork(intx,inty)39【培訓試題】走迷宮2349Description有一個m*n格的迷宮(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件讀入這m*n個數(shù)據(jù)和起始點、結束點(起始點和結束點都是用兩個數(shù)據(jù)來描述的，分別表示這個點的行號和列號)?，F(xiàn)在要你編程找出所有可行的道路，要求所走的路中沒有重復的點，走時只能是上下左右四個方向。如果一條路都不可行，則輸出相應信息(用-l表示無路)。Input第一行是兩個數(shù)m，n，接下來是m行n列由1和0組成的數(shù)據(jù)，最后兩行是起始點和結束點(m,n>1且m,n<15)。Output輸出所有可能路路徑條數(shù)，如果沒有一條可行的路則輸出０。SampleInput561001011111110011101111101110111156SampleOutput：12

【培訓試題】走迷宮2349Description40【模擬試題】最少步數(shù)1800【問題描述】：在各種棋中，棋子的走法總是一定的，如中國象棋中馬走“日”。有一位小學生就想如果馬能有兩種走法將增加其趣味性，因此，他規(guī)定馬既能按“日”走，也能如象一樣走“田”字。他的同桌平時喜歡下圍棋，知道這件事后覺得很有趣，就想試一試，在一個（100*100）的圍棋盤上任選兩點A、B，A點放上黑子，B點放上白子，代表兩匹馬。棋子可以按“日”字走，也可以按“田”字走，倆人一個走黑馬，一個走白馬。誰用最少的步數(shù)走到左上角坐標為(1,1)的點時，誰獲勝。現(xiàn)在他請你幫忙，給你A、B兩點的坐標，想知道兩個位置到（1,1）點的可能最少步數(shù)。輸入：12161810輸出：8

9【模擬試題】最少步數(shù)1800【問題描述】：在各種棋中，棋子的411、確定出發(fā)點從（x,y）出發(fā)通過一次廣度優(yōu)先搜索，可以找到從(x,y)至棋盤上所有可達點的最少步數(shù)。而問題中要求的是黑馬所在的（x1，y1）和白馬所在（x2，y2）到達(1,1)目標點的最少步數(shù)。雖然兩條路徑的起點不一樣，但是它們的終點卻是一樣的。如果我們將終點(1,1)作為起點，這樣只需要一次廣度優(yōu)先搜索便可以得到（x1，y1）和（x2，y2）到達(1,1)的最少步數(shù)。2、數(shù)據(jù)結構設queue—隊列，存儲從(1,1)可達的點（queue[k][1..2]）以及到達該點所需要的最少步數(shù)（queue[k][3]）（0≤k≤192+1）。隊列的首指針為open，尾指針為closed。初始時，queue中只有一個元素為(1,1)，最少步數(shù)為0。S—記錄(1,1)到每點所需要的最少步數(shù)。顯然，問題的答案是s[x1][y2]和s[x2][y2]。初始時，s[1][1]為0，除此之外的所有元素值設為-1。1、確定出發(fā)點42dx、dy—移動后的位置增量數(shù)組。馬有12種不同的擴展方向：馬走“日”：(x-2,y-1)(x-1,y-2)(x-2,y+1)(x-1,y+2)(x+2,y-1)(x+1,y-2)(x+2,y+1)(x+1,y+2)馬走“田”：(x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2)我們將i方向上的位置增量存入常量數(shù)組dx[i]、dy[i]中（1≤i≤12）intdx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};3、約束條件⑴不能越出界外。由于馬的所有可能的落腳點s均在s的范圍內(nèi)，因此一旦馬越出界外，就將其s值賦為0，表示“已經(jīng)擴展過，且(1,1)到達其最少需要0步”。這看上去是荒謬的，但可以簡單而有效地避免馬再次落入這些界外點。⑵該點在以前的擴展中沒有到達過。如果曾經(jīng)到達過，則根據(jù)廣度優(yōu)先搜索的原理，先前到達該點所需的步數(shù)一定小于當前步數(shù)，因此完全沒有必要再擴展下去。由此得出，馬的跳后位置（x,y）是否可以入隊的約束條件是s[x][y]<0dx、dy—移動后的位置增量數(shù)組。馬有12種不同43海上葬禮有一片被大海包圍的群島，島上居住著一個食人部族。很多年前部落里有一位巫師接受了神的召喚跳入海中，從此，那一片海域就被打上了神的烙印，被這片海域所包圍的陸地也被賦予了神圣的意義（包圍關系滿足傳遞性，即海域A包圍了島B，島B包圍了海域C，而海域C中包含了島D，則我們說海域A也包含了島D）。從那以后，部落里的巫師死后都必須葬在這片神圣海域所包圍的島上，而且每一個島都只能埋葬一位巫師（否則就會被視為對神的不敬，從而給部族帶來災難）。現(xiàn)在給你群島的地圖和最初那位巫師跳海的地方，請你計算一下最多可以埋葬多少巫師。海上葬禮有一片被大海包圍的群島，島上居住著一個食人部族。很44地圖是一個n*m的字符矩陣，’#’代表陸地，’.’代表海洋。連通的一片陸地為一個島，連通的一片海洋為一個海域。其中，陸地從上、下、左、右4個方向連通，海洋從上、下、左、右、左上、左下、右上、右下8個方向連通。如下圖。圖3中有4個島，2片海域。如果在A處落水，則落水的海域包圍了除右上、左下兩個頂角外的3個島嶼；如果在B處落水，則只包含了中間的2個島。數(shù)據(jù)范圍是n,m<=500。地圖是一個n*m的字符矩陣，’#’代表陸地，’.’代表海洋。45分析這道題目的思路比較簡單。根據(jù)題意,可分三個步驟處理問題：做一遍floodfill,將最初的巫師落水的海域設立標記,假設為S再做一遍floodfill，將S區(qū)域所包圍的所有區(qū)域（包括海洋和陸地）設立標記，假設為E。在E區(qū)域中做一遍floodfill，統(tǒng)計有多少塊連通的陸地（即島的個數(shù)）現(xiàn)在的問題就是，用什么樣的算法實現(xiàn)floodfill。我們很容易想到深度優(yōu)先遍歷(DFS)的遞歸算法。由于要用遞歸，使用系統(tǒng)堆棧，因此對于500*500個結點的最壞情況下，會造成堆棧溢出，而且所需空間>1000kb，無法滿足題設的空間限制。在這種情況下，我們考慮深度優(yōu)先遍歷的非遞歸過程。分析這道題目的思路比較簡單。根據(jù)題意,可分三個步驟處理問46分析首先給8個方向矢量定一個序號，用一個常量數(shù)組進行記錄： CONSTd:array[1..8,1..2]ofshortint =((-1,-1),(0,-1),(-1,1),(0,1),(1,1),(0,1),(1,-1),(0,-1));建立一個順序棧S，棧的每個元素代表深度優(yōu)先遍歷路徑中的一個結點位置，記錄該位置當前擴展到的方向矢量的序號，再用一對變量Current_x，Current_y記錄棧頂元素所代表的具體位置，就可以以非遞歸的方式完成深度優(yōu)先遍歷了。分析首先給8個方向矢量定一個序號，用一個常量數(shù)組進行記錄：47PROCDfs(startX,startY:integer);初始化棧Current_xstartXCurrent_ystartYtop1;s[top]0;{初始結點入棧}標記(Current_x,Current_y)為已擴展結點whiletop>0do【s[top]st[top]+1if（s[top]<=8）and（按s[top]方向擴展的結點屬于海洋區(qū)域）and（之前沒有擴展過）then【Current_xCurrent_x+d[s[top],1]Current_yCurrent_y+d[s[top],2]標記(Current_x,Current_y)為已擴展結點toptop+1;s[top]0{新結點入棧}】else【toptop-1{當前結點退棧}iftop>0then【Current_xCurrent_x–d[s[top],1]Current_yCurrent_y–d[s[top],2]】】】ENDP

PROCDfs(startX,startY:inte48【培訓試題】最大子序和問題描述輸入一個長度為ｎ的整數(shù)序列（A1,A2,……,An），從中找出一段連續(xù)的長度不超過M的子序列，使得這