寬搜及應(yīng)用舉例

1、 寬搜及應(yīng)用 授課人 江蘇省揚中高級中學(xué) 顧大成例1、最大黑區(qū)域（area.?）黑白位圖是由黑白兩種像素點組成的矩形點陣，圖像識別的一個操作是求出黑白位圖中最大黑區(qū)域的面積。請你設(shè)計一個程序完成這個任務(wù)。黑區(qū)域由黑像素組成，一個黑區(qū)域中的每個像素至少與該區(qū)域中的另一個像素相鄰（僅指上、下、左、右相鄰）。兩個不同的黑區(qū)域沒有相鄰的像素點。一個黑區(qū)域的面積是其所包含的像素點的個數(shù)。輸入：第一行含兩個整數(shù)n和m(1=n,mans then ans:=max; end; writeln(ans);end.Const /dx橫坐標(biāo)、dy橫縱坐標(biāo)變化值 dx:array1.4 of longint=(0,

2、1,0,-1); dy:array1.4 of longint=(1,0,-1,0); var a:array0.101,0.101 of longint; max,ans,i,j,n,m:longint;procedure dfs(i,j:longint);var w:longint;begin ai,j:=0; /訪問過做標(biāo)記 max:=max1; for w:=1 to 4 do /往4個方向拓展 if ai+dxw,j+pdyw=1 then dfs(i+dxw,j+dyw);end;JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例1、最大黑區(qū)域（area.?）樣例輸入：5

3、 60 1 1 0 0 11 1 0 1 0 10 1 0 0 1 00 0 0 1 1 11 0 1 1 1 0樣例輸出：7算法1：dfs 從左上角開始，找到一個黑點（ai,j=1），然后dfs(i,j),dfs到的點置為0，一次dfs完畢得到一個返回值max。主程序中通過打擂臺記錄最大的max給ans，再找（窮舉）下一個點繼續(xù)dfs。算法2：bfs(寬度優(yōu)先搜索)_利用隊列實現(xiàn)JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用寬度優(yōu)先搜索（寬搜，bfs)寬度優(yōu)先搜索算法又稱為廣度優(yōu)先搜索，是最簡便的圖的搜索算法之一，這個算法是很多重要的圖論算法的模型；BFS（Breadth Fir

4、st Search）屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋目標(biāo)節(jié)點（目標(biāo)狀態(tài)）；換句話說，它并不考慮結(jié)果的可能位置，不關(guān)心搜索的快慢好壞，就是徹底地搜索整張圖，直到找到目標(biāo)節(jié)點為止（或者無解）；從算法的觀點看，所有因為展開節(jié)點而得到的子節(jié)點都會被加入到一個先進(jìn)先出的隊列中，所以是隊列的重要應(yīng)用。JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用通過搜索樹，比較bfs與dfs的區(qū)別。白色表示未訪問的節(jié)點，黑色表示已經(jīng)訪問的節(jié)點，灰色表示：DFS中為正在訪問的節(jié)點、BFS中為已入隊等待訪問的節(jié)點。寬度優(yōu)先搜索（寬搜，BFS)JSOI2017省信息學(xué)奧林匹克冬令營基

5、礎(chǔ)班教學(xué)寬搜及應(yīng)用結(jié)構(gòu)一：求一個解、所有解、最優(yōu)解while frontrear then p:=false; end；end;寬度優(yōu)先搜索（寬搜，bfs)JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例1、最大黑區(qū)域（area.?）用bfs怎么做？BFS應(yīng)用舉例 for i:=1 to n do for j:=1 to m do if ai,j=1 then begin front:=1; rear:=1;qf,1:=i; qf,2:=j; ai,j:=0; /從(i,j)開始寬搜 while frontans then ans:=rear; /打擂臺求出最優(yōu)解 end;Var

6、q:array1.10000,1.2of longint;JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例2、瓷磚（tile.?，分班考試）BFS應(yīng)用舉例 在一個w*h的矩形廣場上，每一塊1*1的地面都鋪設(shè)了紅色或黑色的瓷磚。小Y同學(xué)站在某一塊黑色的瓷磚上，他可以從此處出發(fā)，移動到上下左右四個相鄰的、且是黑色的瓷磚上?，F(xiàn)在，他想知道，通過重復(fù)上述移動所能經(jīng)過的黑色瓷磚數(shù)。輸入： 第一行為h、w，2=w、h=50，之間有一個空格隔開； 以下為一個w行h列的二維字符矩陣，每個字符為“.”、“#”、“”，分別表示該位置為黑色的瓷磚、紅色的瓷磚、以及小Y的初始位置。輸出： 輸出一行一個整數(shù)

7、，表示小Y從初始位置出發(fā)可以到達(dá)的瓷磚數(shù)。JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用小結(jié)1： 以上2個例題，都是說明“寬搜”的一個重要應(yīng)用：求連通性問題。再比如：usaco中的一個經(jīng)典題目“數(shù)水塘”。BFS應(yīng)用舉例JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例3、關(guān)系網(wǎng)絡(luò)（relationship.?） 有n個人，他們的編號為1n，其中有一些人相互認(rèn)識，現(xiàn)在x想要認(rèn)識y，可以通過他所認(rèn)識的人來認(rèn)識更多的人（如果a認(rèn)識b、b認(rèn)識c，那么a可以通過b來認(rèn)識c），求出x最少需要通過多少人才能認(rèn)識y。輸入: 第一行三個整數(shù)n、x、y；接下來一個nn的鄰接矩陣，ai,j=1

8、表示i認(rèn)識j，ai,j=0表示不認(rèn)識。保證i=j時,ai,j=0,并且ai,j=aj,i。輸出: x認(rèn)識y最少需要通過的人數(shù)。數(shù)據(jù)保證x一定能認(rèn)識y 。樣例輸入：5 1 50 1 0 0 01 0 1 1 00 1 0 1 00 1 1 0 10 0 0 1 0樣例輸出：2BFS應(yīng)用舉例JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例3、關(guān)系網(wǎng)絡(luò)（relationship.?）算法分析： 寬搜。 先設(shè)答案ans=0。把x加入隊列并設(shè)置為隊頭元素，從隊頭開始進(jìn)行寬搜，窮舉鄰接矩陣的第x行，看x認(rèn)識誰（判斷ax,j=1），認(rèn)識的人（j）全部依次入隊，并且ans:=ans+1，如果出現(xiàn)了

9、y，則輸出ans，結(jié)束搜索，否則，取出隊頭元素繼續(xù)寬搜。BFS應(yīng)用舉例JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例3用結(jié)構(gòu)一實現(xiàn)：while frontrear then p:=false;/該題此條件可以省略嗎？end;BFS應(yīng)用舉例JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用小結(jié)2： 本題是說明“寬搜”的另一個重要應(yīng)用：求最優(yōu)值問題。比如最少幾次、最快幾步等！思考：如果要輸出x是通過什么關(guān)系（哪些人）認(rèn)識y的呢？解決：再設(shè)一個數(shù)據(jù)域（或者數(shù)組），記錄當(dāng)前節(jié)點是從哪個節(jié)點擴(kuò)展得到的。BFS應(yīng)用舉例JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例4、迷

10、宮（basic.?） 有一種迷宮,存在如下限制條件：1.迷宮是6*6的；2.迷宮中有3堵平行于x軸或y軸的墻；3.迷宮有一個起點、終點。 如下就是一個例子，圖中S和E表示起點和終點。現(xiàn)在的任務(wù)是編程找一條從起點到終點的最短路徑，但不得越過任何一堵墻。保證有解！BFS應(yīng)用舉例JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用BFS應(yīng)用舉例輸入： 第一行、第二行為起點、終點坐標(biāo)。 第三、四、五行描述3堵墻。前一個坐標(biāo)一定在后一個坐標(biāo)的左/上方。輸出： 輸出一行字符串，用NSEW描述的從起點到終點的最短路徑。樣例：basic.in1 62 60 0 1 01 5 1 61 5 3 5basi

11、c.outNEEESWW JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例4、迷宮（basic.?）算法分析： 首先要處理好“墻”的問題。把每個格子看成一個“點”，如果點（x,y）和他的上、下、左、右4個相鄰點（i,j）之間沒有墻，那么他們就可以一步走到，相當(dāng)于在他們之間連一條邊，具體可以用一個“四維數(shù)組”表示，即：canx,y,i,j=true，否則設(shè)置為false。初始化時，所有的值均為true，同時，為防止出界外圍也加上一圈。讀入3堵墻，把涉及到的格子兩兩之間設(shè)置為false。再設(shè)置一個二維數(shù)組v，表示迷宮（起點、終點、該點走沒走過）。 由于是要求最短路徑，所以，接下來，就是

12、直接的寬度優(yōu)先搜索了。BFS應(yīng)用舉例JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例5、倒油問題（oil.?） 有3個油瓶，容量分別為10斤、7斤、3斤。開始時，10斤的瓶子中裝滿了油，其余為空，現(xiàn)在通過在這3個瓶子中倒來倒去，將10斤油分成2個5斤的。請編程輸出一種最快的倒油方案。比如：10 0 03 7 03 4 36 4 06 1 39 1 09 0 12 7 12 5 35 5 0BFS應(yīng)用舉例JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例5、倒油問題（oil.?）算法分析： 首先，用一個三元組T（x10,x7,x3）來表示一種狀態(tài)，其中x10，x7，x3分別

13、表示10斤瓶、7斤瓶、3斤瓶中的油量。 下面，考慮如何實現(xiàn)狀態(tài)之間的轉(zhuǎn)移。有如下6種倒油的可能性：10斤的瓶子往7斤的瓶子里倒：條件是(x100) and (x70) and (x33) 操作是x10:=x10+x3-3;x3:=3;x7不變7斤的瓶子往3斤的瓶子里倒：?7斤的瓶子往10斤的瓶子里倒：?3斤的瓶子往7斤的瓶子里倒：?3斤的瓶子往10斤的瓶子里倒：?BFS應(yīng)用舉例JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例5、倒油問題（oil.?）算法分析： 第三、在沒有找到解（沒出現(xiàn)目標(biāo)狀態(tài)）之前，是不知道該怎么倒油的，也就是說從當(dāng)前狀態(tài)到在一個狀態(tài)是盲目的，只能窮舉。如何窮舉

14、、如何保存每一個狀態(tài)呢？隊列！ 第四、由于是要輸出最快的倒油方案，所以不應(yīng)該做無謂的倒油操作，也就是說從一個狀態(tài)采用一種倒油方法得到的狀態(tài)不能出現(xiàn)過，否則一定不是最快的倒油方案。所以，需要對狀態(tài)“判重”。如何實現(xiàn)？窮舉！ 第五、因為要輸出具體的倒油步驟，所以要保存各個狀態(tài)之間是怎么轉(zhuǎn)移的，以便找到目標(biāo)狀態(tài)后倒過來，按照這個線索輸出從初始狀態(tài)到目標(biāo)狀態(tài)。如何實現(xiàn)？再定義一個數(shù)據(jù)域記錄當(dāng)前節(jié)點是從哪個節(jié)點擴(kuò)展得到的，找到目標(biāo)節(jié)點后，倒序把“解路徑”上的節(jié)點另外保存到一個數(shù)組中，最后從初始狀態(tài)輸出到目標(biāo)狀態(tài)。 參考程序BFS應(yīng)用舉例JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用1、（ ）

15、是一種先進(jìn)先出的線性表。A.棧 B.隊列 C.哈希表（散列表） D.二叉樹2、廣度（寬度）優(yōu)先搜索時，需要用到的數(shù)據(jù)結(jié)構(gòu)是（ ）。A.鏈表 B.隊列 C.哈希表（散列表） D.棧3、設(shè)棧S和隊列Q初始狀態(tài)為空，元素e1，e2，e3，e4，e5，e6依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，若出隊的順序為e2，e4，e3，e6，e5，e1，則棧S的容量至少應(yīng)該為（ ）。A.2 B.3 C.4 D.5問題討論（noip初賽試題選講）BJSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例6、猴群（monkey.?）問題描述: 若某矩形由數(shù)學(xué)0到9組成，其中數(shù)字0代表樹，19代表猴子，凡是由0

16、或矩形邊圍起來的區(qū)域表示有一群猴子在這一帶。給定數(shù)字矩形，求矩形中有多少群猴子。輸入:輸入數(shù)據(jù)的第一行為矩形的行數(shù)m和列數(shù)n，后面為一個mn的數(shù)字矩形。輸出:輸出數(shù)據(jù)僅一行，一個數(shù)，表示猴群的數(shù)目。樣例輸入：4 100234500067103456050020456006710000000089樣例輸出：4問題討論JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用0234500067103456050020456006710000000089如果要求最大的猴群中猴群的數(shù)量呢？問題討論JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例7、奇怪的電梯（lift.?） 呵呵，有一天

17、我做了一個夢，夢見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯，而且第i層樓(1=i=N)上有一個數(shù)字Ki(0=Ki=N)。電梯只有四個按鈕：開，關(guān)，上，下。上下的層數(shù)等于當(dāng)前樓層上的那個數(shù)字。當(dāng)然，如果不能滿足要求，相應(yīng)的按鈕就會失靈。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,)，從一樓開始。在一樓，按“上”可以到4樓，按“下”是不起作用的，因為沒有-2樓。那么，從A樓到B樓至少要按幾次按鈕呢？輸入： 輸入文件共有二行，第一行為三個用空格隔開的正整數(shù)，表示N、A、B(1N200, 1A,BN)，第二行為N個用空格隔開的正整數(shù)，表示Ki。輸出： 輸出文件僅一行，即最少按鍵次數(shù),

18、若無法到達(dá)，則輸出-1。樣例輸入：5 1 53 3 1 2 5樣例輸出：3 問題討論JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用算法分析： 因為要求的是“最少按幾次按扭”，所以是很明顯的寬度優(yōu)先搜索。每次從當(dāng)前結(jié)點最多只可以擴(kuò)展兩個結(jié)點。問題討論JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用問題討論JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用例8、產(chǎn)生數(shù)（produce.?） 給出一個整數(shù)n（n2000）和k個變換規(guī)則（k15）。規(guī)則： 1個數(shù)字可以變換成另一個數(shù)字； 規(guī)則中，右邊的數(shù)字不能為零。 例如：n=234，k=2，規(guī)則為 25 36 上面的整數(shù)234經(jīng)過變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)）234、534、264、562共4種不同的產(chǎn)生數(shù)。求經(jīng)過任意次的變換（0次或多次），能產(chǎn)生出多少個不同的整數(shù)。僅輸出不同整數(shù)的個數(shù)。樣例輸入：23422 53 6樣例輸出：4例9、狼羊菜過河問題例10、牧師與野人過河問題問題討論JSOI2017省信息學(xué)奧林匹克冬令營基礎(chǔ)班教學(xué)寬搜及應(yīng)用寬搜的缺點：隨著搜索層數(shù)的增加，空間開銷非常大。同時設(shè)置兩個隊列，其中一個隊列從初始狀態(tài)開始拓展，另一個隊列從末狀態(tài)開始拓展，直到兩個隊列出現(xiàn)交集。雙向?qū)捤涯苡行У亟档蜁r間復(fù)