【題目描述】

一天Extense在森林里探險(xiǎn)的時(shí)候不小心走入了一個(gè)迷宮，迷宮可以看成是由n×n的格點(diǎn)組成，每個(gè)格點(diǎn)只有2種狀態(tài)，‘.’和‘#’，前者表示可以通行后者表示不能通行。同時(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è)不能通行(為‘#’)，則看成無(wú)法辦到。

【輸入】

第1行是測(cè)試數(shù)據(jù)的組數(shù)k，后面跟著k組輸入。每組測(cè)試數(shù)據(jù)的第1行是一個(gè)正整數(shù)n(1≤n≤100)，表示迷宮的規(guī)模是n×n的。接下來(lái)是一個(gè)n×n的矩陣，矩陣中的元素為‘.’或者‘#’。再接下來(lái)一行是4個(gè)整數(shù)ha,la,hb,lb，描述A處在第ha行, 第la列，B處在第hb行, 第lb列。注意到ha,la,hb,lb全部是從0開(kāi)始計(jì)數(shù)的。

【輸出】

k行，每行輸出對(duì)應(yīng)一個(gè)輸入。能辦到則輸出“YES”，否則輸出“NO”。

思路在代碼中

#include<bits/stdc++.h> using namespace std; int n; bool ans,vis[105][105];//ans代表最終結(jié)果，vis則是搜索中的判斷 char a[105][105];//存儲(chǔ)迷宮 struct app{int x;int y; }; app walk[5];//行走方式 app be,en;//be為起點(diǎn)坐標(biāo)，en為終點(diǎn)坐標(biāo) void bfs(int x,int y){queue<app> Q;app q={x,y};Q.push(q);while(!Q.empty()){app bq=Q.front();//隊(duì)最前坐標(biāo) if(bq.x==en.x&&bq.y==en.y){//搜索到 ans=1;return ;}for(int i=1;i<=4;i++){app aq;int bx=bq.x+walk[i].x,by=bq.y+walk[i].y;if(bx<=n&&bx>=1&&by>=1&&by<=n){if(!vis[bx][by]&&a[bx][by]=='.'){//入隊(duì)列條件判斷 vis[bx][by]=1;aq.x=bx;aq.y=by;Q.push(aq);//入隊(duì) }} }Q.pop();//出對(duì) }return ; } int main(){int k;cin>>k;walk[1].x=1;walk[2].x=-1;walk[3].x=0;walk[4].x=0;walk[1].y=0;walk[2].y=0;walk[3].y=1;walk[4].y=-1;//初始移動(dòng)方式 for(int i=1;i<=k;i++){ans=0;cin>>n;memset(vis,0,sizeof(vis));//這步必須，否則與上一次搜索重復(fù) for(int j=1;j<=n;j++){for(int l=1;l<=n;l++){cin>>a[j][l];}}cin>>be.x>>be.y>>en.x>>en.y;be.x+=1;be.y+=1;en.x+=1;en.y+=1;//統(tǒng)一加一，方便處理邊界 vis[be.x][be.y]=0;//起點(diǎn)先標(biāo)記 bfs(be.x,be.y);if(ans){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【信息学奥赛一本通】1215：迷宫(bfs版)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。