廣度優(yōu)先搜索:走迷宮

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

typedef struct
{
    int r;
    int c;
    int step;
}LOC;//點(diǎn)的屬性

typedef struct
{
    int sr, sc, er, ec;
}POR;//傳送門的屬性

char buf[1000];
char map[101][101];//地圖
int N, M, W;
queue<LOC> Q;//點(diǎn)的隊(duì)列
vector<POR> P;//存儲(chǔ)所有的傳送門信息
int sr, sc, er, ec;//start, end, row, col
int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};//代表四個(gè)方向

void addLOC(int r, int c, int step)
{
    LOC tmp;
    tmp.c = c;
    tmp.r = r;
    tmp.step = step;
    Q.push(tmp);
    map[r][c] = '2';
}//在隊(duì)列中添加一個(gè)點(diǎn)唉匾,并在地圖上留下標(biāo)記‘2’孕讳,防止重復(fù)(0表示可以走,1表示墻巍膘,2表示走過(guò))

void solve()
{
    int i;
    addLOC(sr, sc, 0);//添加第一個(gè)點(diǎn)(起點(diǎn))
here:
    while(!Q.empty())
    {
        LOC cur = Q.front();//提取這個(gè)點(diǎn)的信息
        Q.pop();//處理后便可以退出隊(duì)列
        if(cur.c == ec && cur.r == er)
        {
            cout << cur.step << endl;
            return;
        }//如果到達(dá)終點(diǎn)厂财,就輸出當(dāng)前的步數(shù)
        for(i = 0; i < W; ++i)
        {
            if(P[i].sr == cur.r && P[i].sc == cur.c)
            {
                if(map[P[i].er][P[i].ec] == '0')
                    addLOC(P[i].er, P[i].ec, cur.step+1);
                goto here;
            }
        }//遍歷傳送門,如果踩到了峡懈,而且傳送到的地方不是墻也沒(méi)有走過(guò)璃饱,就添加這個(gè)點(diǎn),繼續(xù)看隊(duì)列中的下一個(gè)點(diǎn)
        //否則此路不通肪康,看隊(duì)列中的下一個(gè)點(diǎn)
        int tmpr, tmpc, i;
        for(i = 0; i < 4; ++i)
        {
            tmpr = cur.r+dir[i][0];
            tmpc = cur.c+dir[i][1];
            if(tmpr>=0 && tmpr<N && tmpc>=0 && tmpc<M && map[tmpr][tmpc]=='0')
            {
                addLOC(tmpr, tmpc, cur.step+1);
            }
        }//嘗試四個(gè)方向荚恶,如果某個(gè)方向有路(不是墻也沒(méi)有到地圖外也沒(méi)有走過(guò)),就添加這個(gè)點(diǎn)
    }
    cout << "die" << endl;//如果一直都沒(méi)有return磷支,輸出die
}
//廣度優(yōu)先搜索谒撼,使用隊(duì)列實(shí)現(xiàn)

int main()
{
    //freopen("data.txt", "r", stdin);
    int num, i;
    cin >> num;
    while(num--)
    {
        P.clear();//把上一個(gè)case的陷阱信息置空
        while(!Q.empty())
            Q.pop();//把上一個(gè)case的點(diǎn)的隊(duì)列置空置空
        cin >> N >> M;//輸入行和列數(shù)
        gets(buf);//吃掉回車
        for(i = 0; i < N; ++i)
            gets(map[i]);//讀入地圖
        cin >> W;//傳送門個(gè)數(shù)
        for(i = 0; i < W; ++i)
        {
            POR tmp;
            cin >> tmp.sr >> tmp.sc >> tmp.er >> tmp.ec;
            P.push_back(tmp);
        }//讀入傳送門并把它加入數(shù)組
        cin >> sr >> sc >> er >> ec;//輸入起點(diǎn)和終點(diǎn)的行,列
        solve();//調(diào)用函數(shù)解決迷宮
    }
    return 0;
}


solve()函數(shù)采用深度優(yōu)先搜索算法雾狈,遍歷離當(dāng)前點(diǎn)最近的點(diǎn)(或傳送門到達(dá)的點(diǎn))加入隊(duì)列廓潜,被加入的點(diǎn)在與“推出它的點(diǎn)”同步數(shù)的點(diǎn)被處理完之前都不會(huì)被處理,換句話說(shuō)善榛,處理一個(gè)點(diǎn)過(guò)后可能會(huì)在隊(duì)尾加入數(shù)個(gè)點(diǎn)(也可能不加入)辩蛋,加入后需要做的是繼續(xù)提取隊(duì)頭的點(diǎn)進(jìn)行操作。廣度優(yōu)先可以想象為河流的分流過(guò)程锭弊。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末堪澎,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子味滞,更是在濱河造成了極大的恐慌樱蛤,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,865評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件剑鞍,死亡現(xiàn)場(chǎng)離奇詭異昨凡,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)蚁署,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,296評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門便脊,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人光戈,你說(shuō)我怎么就攤上這事哪痰∷煸” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,631評(píng)論 0 364
  • 文/不壞的土叔 我叫張陵晌杰,是天一觀的道長(zhǎng)跷睦。 經(jīng)常有香客問(wèn)我,道長(zhǎng)肋演,這世上最難降的妖魔是什么抑诸? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,199評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮爹殊,結(jié)果婚禮上蜕乡,老公的妹妹穿的比我還像新娘。我一直安慰自己梗夸,他們只是感情好层玲,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,196評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著绒瘦,像睡著了一般称簿。 火紅的嫁衣襯著肌膚如雪扣癣。 梳的紋絲不亂的頭發(fā)上惰帽,一...
    開(kāi)封第一講書(shū)人閱讀 52,793評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音父虑,去河邊找鬼该酗。 笑死,一個(gè)胖子當(dāng)著我的面吹牛士嚎,可吹牛的內(nèi)容都是我干的呜魄。 我是一名探鬼主播,決...
    沈念sama閱讀 41,221評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼莱衩,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼爵嗅!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起笨蚁,我...
    開(kāi)封第一講書(shū)人閱讀 40,174評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤睹晒,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后括细,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體伪很,經(jīng)...
    沈念sama閱讀 46,699評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,770評(píng)論 3 343
  • 正文 我和宋清朗相戀三年奋单,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了锉试。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,918評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡览濒,死狀恐怖呆盖,靈堂內(nèi)的尸體忽然破棺而出拖云,到底是詐尸還是另有隱情,我是刑警寧澤应又,帶...
    沈念sama閱讀 36,573評(píng)論 5 351
  • 正文 年R本政府宣布江兢,位于F島的核電站,受9級(jí)特大地震影響丁频,放射性物質(zhì)發(fā)生泄漏杉允。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,255評(píng)論 3 336
  • 文/蒙蒙 一席里、第九天 我趴在偏房一處隱蔽的房頂上張望叔磷。 院中可真熱鬧,春花似錦奖磁、人聲如沸改基。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,749評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)秕狰。三九已至,卻和暖如春躁染,著一層夾襖步出監(jiān)牢的瞬間鸣哀,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,862評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工吞彤, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留我衬,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,364評(píng)論 3 379
  • 正文 我出身青樓饰恕,卻偏偏與公主長(zhǎng)得像挠羔,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子埋嵌,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,926評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 找到他們家的時(shí)候,我已經(jīng)在巷子里面轉(zhuǎn)暈了俐银。 島城的老街就是這樣尿背,單行線多,卻沒(méi)有一條規(guī)律的主干線捶惜,七拐八拐的田藐,每條...
    葉泱曲庸閱讀 536評(píng)論 0 6
  • 洗完澡,兩個(gè)兒子一起高興地走迷宮,走著走著小兒子突然大聲哭起來(lái)了汽久。 我問(wèn)他:“航航鹤竭,你怎么了?”航航一邊擦著鼻涕景醇,...
    蘇_8ab1閱讀 307評(píng)論 0 1
  • 輸入對(duì)應(yīng)數(shù)字可以進(jìn)入對(duì)應(yīng)的模塊: 將各個(gè)模塊寫(xiě)成分函數(shù) 進(jìn)行調(diào)用 首界面代碼: #include #include...
    松愛(ài)家的小秦閱讀 321評(píng)論 0 0
  • 需求 以上是一個(gè)簡(jiǎn)單的3層數(shù)倉(cāng)運(yùn)行調(diào)度臀稚,我們希望ods表有任何一張表etl錯(cuò)誤,不再進(jìn)行后續(xù)的edw和rst層的作...
    長(zhǎng)振閱讀 1,398評(píng)論 0 1
  • 中午給涵涵做了迷糊三痰,要和她再見(jiàn)的時(shí)候吧寺,10個(gè)月的小鬼在床上爬過(guò)來(lái),扶著一邊的欄桿散劫,一只小手使勁向我揮手稚机。 ...
    錢塘樵夫閱讀 163評(píng)論 0 1