簡(jiǎn)介

老規(guī)矩，先來(lái)介紹一下什么是廣度優(yōu)先搜索（至于這么長(zhǎng)時(shí)間沒(méi)更新是為什么，我放在文章結(jié)尾了，感興趣可以看看，以后也是如此）

廣度優(yōu)先搜索，從名字就能聽(tīng)出來(lái)，他和深度優(yōu)先搜索關(guān)系匪淺，沒(méi)錯(cuò)，他們是“孿生兄弟”。兩者雖然是“孿生兄弟”但差別可是巨大無(wú)比：一個(gè)會(huì)深入每一條路徑，也就是“不撞南墻不回頭”；而另一個(gè)則側(cè)重于搜索的廣泛性。這么說(shuō)吧一個(gè)是線(xiàn)性的搜索，另一個(gè)是面性的搜索。

接下來(lái)就是詳細(xì)的解釋了

廣度優(yōu)先搜索，以一個(gè)點(diǎn)為中心，不斷向周?chē)剿?#xff0c;先探索中心點(diǎn)的周?chē)膫€(gè)格子，再將中心按順序轉(zhuǎn)為一個(gè)個(gè)新的格子，再向自己的周?chē)剿?.....就這樣循環(huán)，向周?chē)鷶U(kuò)散式探索；比如指定A為中心點(diǎn)，先探索A四周的格子，依次為B、C、D、E。完成后再將中心點(diǎn)轉(zhuǎn)為B，繼續(xù)探索B的四周（探索過(guò)的除外）為1、2、3。再轉(zhuǎn)為C，探索四周，轉(zhuǎn)為D，探索四周，轉(zhuǎn)為E，探索四周，再繼續(xù)轉(zhuǎn)為1，探索四周......2......3......這樣循環(huán)下去，不理解的可以自己動(dòng)手畫(huà)個(gè)圖，會(huì)對(duì)理解有幫助。

正文開(kāi)始

迷宮出口

題目描述 ：一天Extense在森林里探險(xiǎn)的時(shí)候不小心走入了一個(gè)迷宮，迷宮可以 看成是由 n×n 的格點(diǎn)組成，每個(gè)格點(diǎn)只有 2 種狀態(tài)， 0 和 1，前者表示可以通行后者表示不能通行。同時(shí)當(dāng)Extense處在某個(gè)格點(diǎn)時(shí)，他只能移動(dòng)到東南西北(或者說(shuō)上下左右)四個(gè)方向之一的相鄰格點(diǎn)上，Extense想要從點(diǎn) A 走到點(diǎn) B ， 問(wèn)在不走出迷宮的情況下能不能辦到。 如果起點(diǎn)或者終點(diǎn)有一個(gè)不能通行(為 11)，則看成無(wú)法辦到。

輸入 第 1 行是一個(gè)正整數(shù) n (1≤n≤100)，表示迷宮的規(guī)模是 n×n 的。 接下來(lái)是一個(gè) n×n 的矩陣，矩陣中的元素為 0 或者 1。 再接下來(lái)一行是 4 個(gè)整數(shù) 表示入口和出口的坐標(biāo)。 輸出： 能辦到則輸出 YES，否則輸出 NO。

樣例

輸入復(fù)制

3

0 1 1

0 0 1

1 0 0

1 1 3 3

輸出復(fù)制

YES

#include<bits/stdc++.h>
using namespace std;
int a[110][110]={0};
int x[110]={0};
int y[110]={0};
int n=0;
int q=0,p=0;
int s1,s2,e1,e2;
bool jian_ce(int,int);
int main()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>a[i][j];}}cin>>s1>>s2>>e1>>e2;s1--;s2--;e1--;e2--;q++;x[q]=1;y[q]=1;p++;while(true){if(a[x[p]+1][y[p]]!=1&&x[p]+1<n){q++;x[q]=x[q-1]+1;y[q]=y[q-1];if(jian_ce(x[q],y[q])==true)return 0;}if(a[x[p]][y[p]+1]!=1&&y[p]+1<n){q++;x[q]=x[q];y[q]=y[q]+1;if(jian_ce(x[q],y[q])==true)return 0;}if(a[x[p]-1][y[p]]!=1&&x[p]-1>=0){q++;x[q]=x[q]-1;y[q]=y[q];if(jian_ce(x[q],y[q])==true)return 0;}if(a[x[p]][y[p]-1]!=1&&y[p]-1>=0){q++;x[q]=x[q];y[q]=y[q]-1;if(jian_ce(x[q],y[q])==true)return 0;}p++;}cout<<"NO";return 0;
}
bool jian_ce(int t1,int t2)
{if(t1==e1&&t2==e2){cout<<"YES";return true;}return false;
}

至于為什么沒(méi)更新，因?yàn)?........懶得q(≧▽≦q)