?小鼠迷宮問題

Time Limit:?2 Sec??Memory Limit:?64 MB
Submit:?1??Solved:?1
[Submit][Status][Web Board]

Description

小鼠a與小鼠b身處一個m×n的迷宮中，如圖所示。每一個方格表示迷宮中的一個房間。這m×n個房間中有一些房間是封閉的，不允許任何人進入。在迷宮中任何位置均可沿上，下，左，右4個方向進入未封閉的房間。小鼠a位于迷宮的(p，q)方格中，它必須找出一條通向小鼠b所在的(r，s)方格的路。請幫助小鼠a找出所有通向小鼠b的最短道路。

?

請編程對于給定的小鼠的迷宮，計算小鼠a通向小鼠b的所有最短道路。

Input

本題有多組輸入數據，你必須處理到EOF為止。 每組數據的第一行有3個正整數n，m，k，分別表示迷宮的行數，列數和封閉的房間數。接下來的k行中，每行2個正整數，表示被封閉的房間所在的行號和列號。最后的2行，每行也有2個正整數，分別表示小鼠a所處的方格(p，q)和小鼠b所處的方格(r，s)。

Output

對于每組數據，將計算出的小鼠a通向小鼠b的最短路長度和有多少條不同的最短路輸出。每組數據輸出兩行，第一行是最短路長度；第2行是不同的最短路數。每組輸出之間沒有空行。 如果小鼠a無法通向小鼠b則輸出“No Solution!”。

Sample Input

8 8 3

3 3

4 5

6 6

2 1

7 7

?

Sample Output

11

96

?　　這是道搜索題，要求輸出矩陣內a到b點的最短路長度，以及最短路的條數，并且要繞過限定的“封閉房間”，即某些格子無法走。

　　還可參照?ytu 2463:給小鼠補充代碼?同樣的題，不同的考察形式。

?

1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 int f[100][100]; 5 int ax,ay; 6 int bx,by; 7 int dx[4]={0,1,0,-1}; 8 int dy[4]={1,0,-1,0}; 9 int _count=0; 10 int _min=9999999; 11 int n,m,k; 12 13 void dfs(int d,int t,int curx,int cury) 14 { 15 if(t>_min) 16 return ; 17 if(curx<0 || cury<0 || curx>n-1 || cury>m-1) 18 return ; 19 if(cury==by && curx==bx){ 20 if(t<_min){ 21 _count=1; 22 _min=t; 23 } 24 else{ 25 _count++; 26 } 27 return ; 28 } 29 for(int i=0;i<4;i++){ 30 if(curx+dx[i]<0 || cury+dy[i]<0) continue; 31 if(!f[curx+dx[i]][cury+dy[i]]){ 32 f[curx+dx[i]][cury+dy[i]]=true; 33 dfs(i,t+1,curx+dx[i],cury+dy[i]); 34 f[curx+dx[i]][cury+dy[i]]=false; 35 } 36 } 37 38 return ; 39 } 40 41 int main() 42 { 43 while(cin>>n>>m>>k){ 44 _count=0; 45 _min=99999999; 46 memset(f,0,sizeof(f)); 47 for(int i=1;i<=k;i++){ 48 int a,b; 49 cin>>a>>b; 50 f[a][b]=true; 51 } 52 cin>>ax>>ay; 53 cin>>bx>>by; 54 dfs(-1,0,ax,ay); 55 cout<<_min<<endl; 56 cout<<_count<<endl; 57 } 58 return 0; 59 }

?

?

Freecode : www.cnblogs.com/yym2013

轉載于:https://www.cnblogs.com/yym2013/p/3485006.html

總結

以上是生活随笔為你收集整理的ytu 1980:小鼠迷宫问题（DFS 深度优先搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。