第八屆藍橋杯Java A組第一題迷宮題解

題目描述

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

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

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

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

L表示走到左邊的房間，

R表示走到右邊的房間，

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

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

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

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

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

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

迷宮地圖如下：

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
           

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

而不是在裡邊兜圈子。

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

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

題目解析：

這道題難度應該不算大，簡單的dfs深搜題，需要注意的是在dfs函數中我們需要先考慮邊界情況，然後根據目前的字母來判斷接下來應該往哪個方向走，在這裡我們繼續調用dfs函數即可，在主函數中，輸入二維字元數組采用固定的套路用toCharArray進行轉換。因為本題沒有初始的起點，是以在主函數裡我們通過兩層循環一個點一個點的進行周遊深搜，最後得出結果。

參考代碼：

import java.util.Scanner;

/**
  * 迷宮探索
 * @author autumn_leaf
 * @Date 2019/03/23
 */
public class ExploreMazes {
	
	static char[][] maze = new char[11][11];
	static int[][] vis = new int[10][10];
	static int ans = 0;
	
	//深搜函數
	static void dfs(int i,int j) {
		//走到了邊界
		if(i==-1 || i==10 || j==-1 || j==10) {
			ans++;
			return;
		}
		if(vis[i][j] ==1)
			return ;
		vis[i][j] = 1;
		char ch = maze[i][j];
		//上下左右四個方向
		if(ch == 'U')
			dfs(i-1,j);
		if(ch == 'D')
			dfs(i+1,j);
		if(ch == 'L')
			dfs(i,j-1);
		if(ch == 'R')
			dfs(i,j+1);
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		//輸入二維字元數組
		for(int i=0; i<10; i++) {
			String temp = sc.nextLine();
			maze[i] = temp.toCharArray();
		}
		for(int i=0; i<10; i++) {
			for(int j=0 ;j<10; j++) {
				//初始化
				vis = new int[10][10];
				dfs(i,j);
			}
		}
		System.out.println(ans);
	}

}
           

最終得到的結果為：31

好了，本題題解就到這裡了，有疑惑的同學可以在下方評論區留言哦！