27行程式碼AC_迷宮 2017年第八屆藍橋杯A組第一題（暴力、仿迷宮）

題目描述

X星球的一處迷宮遊樂場建在某個小山坡上。
它是由10x10相互連通的小房間組成的。
房間的地板上寫著一個很大的字母。
我們假設玩家是面朝上坡的方向站立，則：
L表示走到左邊的房間，
R表示走到右邊的房間，
U表示走到上坡方向的房間，
D表示走到下坡方向的房間。
 
X星球的居民有點懶，不願意費力思考。
他們更喜歡玩運氣類的遊戲。這個遊戲也是如此！
 
開始的時候，直升機把100名玩家放入一個個小房間內。
玩家一定要按照地上的字母移動。
迷宮地圖如下：

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR

請你計算一下，最後，有多少玩家會走出迷宮?
而不是在裡邊兜圈子。

---

分析與思考

第一眼看上去以為是搜尋， 讀完題發現是一道暴力列舉題。

思路：
先思考一下，若迷宮規模為n，則某點在迷宮中最多隻能走 n*n步(蛇形)， 因此， 在對每個點遍歷時，可以用num記錄步數，當num超過n*n+5後，表明這條路沒辦法走出去， 反之，如果在遍歷期間i或j越界，則說明可以走出去。 最後統計總數即可。

改進：

1. 可以設定一個與迷宮規模等大的二維int陣列， 全部置0， 如果某點能走通， 則置1， 這樣，在遍歷每個點前，先判斷對應的int陣列是否等於1， 若等於1， 則直接結束此次迴圈， 會大大提高效率。
2. 使用define定義陣列的規模， 可以在測試時方便的調節陣列大小。

---

程式碼展示

#include<bits/stdc++.h>
#define N 10
using namespace std;
char a[N][N];			//記錄迷宮 
int b[N][N];			//如果該點可以走通，則置1。 
int main() {
	for(int i = 0; i < N; i++)  cin>>a[i]; 	//輸入迷宮
	 
	memset(b, 0, sizeof(b));
	int sum1 = 0;		//記錄能走出去的次數 
	
	for(int i = 0; i < N; i++) 	//遍歷 
		for(int j = 0; j < N; j++) {
			int sum = 0;
			int i1=i, j1=j;		//代替i，j進行值的變化 
			while(sum < N*N+10) {	 
				if(b[i1][j1]==1) break;	//如果走到的這個點 b[i][j]=1，則代表能走出去 
				sum++;
				if(a[i1][j1] == 'U') i1--;
				else if(a[i1][j1] == 'D') i1++;
				else if(a[i1][j1] == 'L') j1--;
				else if(a[i1][j1] == 'R') j1++;
				
				if(i1<0 || i1>=N || j1<0 || j1>=N)  break;
			}
			if(sum != N*N+10) { sum1++; b[i][j]=1; } 	//如果sum遍歷到頭，則說明走不出去 
		}
	cout << sum1 << endl;
return 0; } 

這世界就是，一些人總在晝夜不停的努力，而另外一些人，起床就發現世界已經變了。 加油，陌生人！