題目：
試題 E: 迷宮
本題總分：15 分
【問題描述】
下圖給出了一個迷宮的平面圖，其中標記為 1 的為障礙，標記為 0 的為可
以通行的地方。
010000
000100
001001
110000
迷宮的入口為左上角，出口為右下角，在迷宮中，只能從一個位置走到這
個它的上、下、左、右四個方向之一。
對于上面的迷宮，從入口開始，可以按DRRURRDDDR 的順序通過迷宮，
一共 10 步。其中 D、U、L、R 分別表示向下、向上、向左、向右走。
對于下面這個更復雜的迷宮（30 行 50 列），請找出一種通過迷宮的方式，
其使用的步數最少，在步數最少的前提下，請找出字典序最小的一個作為答案。
請注意在字典序中D<L<R<U。（如果你把以下文字復制到文本檔案中，請務
必檢查復制的內容是否與檔案中的一致。在試題目錄下有一個檔案 maze.txt，
內容與下面的文本相同）
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
試題E: 迷宮 7
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一
個字串，包含四種字母 D、U、L、R
#include<iostream>
using namespace std;
int v[101][101]={0};
char map[101][101];
int que[100000][4];//que[x][0]和que[x][1]分別表示 橫縱坐標， que[x][2]和que[x][3]分別代表走的方向和前驅
int d[4][3]={0,1,1,0,-1,2,-1,0,3,1,0,4};//表示上下左右變化，用1-D,2-L, 3-R,4-U
void dayin(int x){
if(que[x][3]!=0)
{
dayin(que[x][3]);
cout<<que[x][2]<<" ";
}
cout<<"a"<<" ";
}
int main()
{ FILE *f=fopen("maze.txt","r");
for(int i=1;i<=30;i++) fscanf(f,"%s",&map[i]); int head=0;
int tail=1;
que[1][0]=1; //將起始點入隊 que[1][1]=1;
que[1][2]=0; que[1][3]=0; while(head<tail)
{ head++; int x=que[head][0]; int y=que[head][1]; for(int i=0;i<4;i++) { int x1=x+d[i][0]; int y1=y+d[i][1]; if(1<=x1&&x1<30&&1<=y1&&y1<50&&v[x1][y1]==0&& map[x1][y1]=='0') { que[tail][0]=x1; que[tail][1]=y1; que[tail][2]=d[i][2];//記錄走的方向 que[tail][3]=head;//記錄前驅 v[x1][y1]=1; tail++; } if(x1==30&&y1==50) { dayin(head);//回溯函式 } } } } 檔案讀取是圖片中資料
uj5u.com熱心網友回復：
代碼有點亂，我重發一個轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/64849.html
標籤：疑難問題