藍橋杯第八屆C/C++ A組省賽（2017）第一題：迷宮

标題：迷宮

X星球的一處迷宮遊樂場建在某個小山坡上。

它是由10x10互相連通的小房間組成的。

房間的地闆上寫着一個很大的字母。

我們假設玩家是面朝上坡的方向站立，則：

L表示走到左邊的房間，

R表示走到右邊的房間，

U表示走到上坡方向的房間，

D表示走到下坡方向的房間。

X星球的居民有點懶，不願意費力思考。

他們更喜歡玩運氣類的遊戲。這個遊戲也是如此！

開始的時候，直升機把100名玩家放入一個個小房間内。

玩家一定要按照地上的字母移動。

迷宮地圖如下：

------------

UDDLUULRUL

UURLLLRRRU

RRUURLDLRD

RUDDDDUUUU

URUDLLRRUU

DURLRLDLRL

ULLURLLRDU

RDLULLRDDD

UUDDUDUDLL

ULRDLUURRR

------------

請你計算一下，最後，有多少玩家會走出迷宮? 

而不是在裡邊兜圈子。

請送出該整數，表示走出迷宮的玩家數目，不要填寫任何多餘的内容。

如果你還沒明白遊戲規則，可以參看一個簡化的4x4迷宮的解說圖：

p1.png

解題思路： 從題目可知一定需要dfs，這裡采用從終點出發（從出口）反向逆推出所有可走出迷宮的房間。主函數周遊四條邊，如下底邊為down的一定為出口，那麼就從出口走入。周遊房間的四個方向（當然設定有邊界判斷，在邊界的房間隻判斷三個方向）若左邊的房間為右邊的箭頭（R）則一定是通路。總之就是逆着箭頭走。然後把所有出口都深度搜尋一遍，由于資料規模小。是以不用在乎重複走的标記。走過隻需記錄即可。最後統計整個地圖的标記數就是答案

為 31

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<windows.h>
char* a[10]={"UDDLUULRUL",
			"UURLLLRRRU",
			"RRUURLDLRD",
			"RUDDDDUUUU",
			"URUDLLRRUU",
			"DURLRLDLRL",
			"ULLURLLRDU",
			"RDLULLRDDD",
			"UUDDUDUDLL",
			"ULRDLUURRR"};
bool succe [10][10];
int count=0,d=0;
void run(int y,int x)
{
	int i,j;
	succe[y][x]=1;
	if((y-1)!=-1 && a[y-1][x]=='D')
		run(y-1,x);
	if((y+1)!=10 && a[y+1][x]=='U')
		run(y+1,x);
	if((x+1)!=10 && a[y][x+1]=='L')
		run(y,x+1);
	if((x-1)!=-1 && a[y][x-1]=='R')
		run(y,x-1);
}


int main()
{
	int i,j;
	memset(succe,0,sizeof(succe));
	for(j=0;j<10;j++)
		if(a[0][j]=='U')
			run(0,j);
	for(j=0;j<10;j++)
		if(a[9][j]=='D')
			run(9,j);
	for(j=0;j<10;j++)
		if(a[j][0]=='L')
			run(j,0);
	for(j=0;j<10;j++)
		if(a[j][9]=='R')
			run(j,9);
	for(i=0;i<10;i++)
		for(j=0;j<10;j++)
			if(succe[i][j]==1)
				count++;
	printf("%d",count);
	return 0;
}