1215：迷宮

時(shí)間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 29437 ??? 通過數(shù): 8772

【題目描述】

一天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)到東南西北(或者說上下左右)四個(gè)方向之一的相鄰格點(diǎn)上，Extense想要從點(diǎn)A走到點(diǎn)B，問在不走出迷宮的情況下能不能辦到。如果起點(diǎn)或者終點(diǎn)有一個(gè)不能通行(為#)，則看成無法辦到。

【輸入】

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

【輸出】

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

【輸入樣例】

2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0

【輸出樣例】

YES NO

【分析】

? ? ? ? 走迷宮問題是DFS經(jīng)典問題，這道題用深搜（DFS）容易超時(shí)，最好用廣搜（BFS），因?yàn)轭}目只需要判斷是否存在通路，并未要求找出所有通路，故使用BFS最佳，但本題放在DFS處，需要注意以下幾個(gè)問題。

（1）探索四個(gè)方向，避免重復(fù)遍歷通常采用以下三種方法。

• 類似1191：流感傳染題目，及時(shí)更新矩陣
• 設(shè)置vis數(shù)組，用于記錄訪問標(biāo)記；
• 不做記號(hào)，沿途修改，類似水洼題目，填水坑為平地。http://47.110.135.197/problem.php?id=4255

（2）需要進(jìn)行邊界判斷處理。

【參考代碼】

#include <stdio.h> #include <string.h>char a[105][105]; //迷宮矩陣 int n; //迷宮規(guī)模 int vis[105][105]; //訪問數(shù)組 int ha,la; //起始點(diǎn)坐標(biāo)（A點(diǎn)） int hb,lb; //終止點(diǎn)坐標(biāo)（B點(diǎn)） int dx[4]={0,0,-1,1}; //方向數(shù)組 int dy[4]={-1,1,0,0}; //方向數(shù)組int flag; //狀態(tài)位（終點(diǎn)判斷）void dfs(int x, int y) {int i,nx,ny;if(flag==1){return;}if(x==hb && y==lb) //到達(dá)終點(diǎn) {flag=1;return;}for(i=0;i<4;i++){nx=x+dx[i]; //四個(gè)方向探索，地址偏移ny=y+dy[i];if(flag==0 && nx>=0 && nx<n && ny>=0 && ny<n && a[nx][ny]== '.' && !vis[nx][ny]){vis[nx][ny]=1; //或 去掉vis數(shù)組，直接填坑，a[nx][ny]='#; dfs(nx,ny);//vis[nx][ny]=0; //本題不用回溯，否則超時(shí)}}return; }int main() {int i,j,l,k;scanf("%d",&k);while(k--){scanf("%d",&n);memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));for(i=0;i<n;i++)scanf("%s",&a[i]);scanf("%d %d %d %d",&ha,&la,&hb,&lb);if(a[ha][la]=='#' || a[hb][lb]=='#'){printf("NO\n");flag=0;continue;}dfs(ha,la);if(flag==1)printf ("YES\n");elseprintf ("NO\n");flag=0;}return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1215

?

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

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

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