多益網絡2019校招—鑰匙和房間問題

時間：20180906

題目描述 ：

LeetCode 841. Keys and Rooms

有 N 個房間，開始時你位于 0 号房間。每個房間有不同的号碼：0，1，2，...，N-1，并且房間裡可能有一些鑰匙能使你進入下一個房間。

在形式上，對于每個房間 i 都有一個鑰匙清單 rooms[i]，每個鑰匙 rooms[i][j] 由 [0,1，...，N-1] 中的一個整數表示， 其中 N = rooms.length。 鑰匙 rooms[i][j] = v 可以打開編号為 v 的房間。 

最初，除 0 号房間外的其餘所有房間都被鎖住。你可以自由地在房間之間來回走動。如果能進入每個房間傳回 true，否則傳回 false。要求先寫出解題思路，再編寫代碼。

通過廣度優先搜尋（BFS）的方式進行探索。将可通路的0房間加入隊列之中，通路隊列中的一個元素，周遊他可以到達的房間，如果該房間還不能被通路，那麼設定為通路，否則跳過。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Stack;

public class KeysAndRooms {
	public static void main(String[] args) {
		//[[1],[2],[3],[]]
		List<List<Integer>> rooms = new ArrayList();
		List<Integer> keys0 = new ArrayList<>();
		keys0.add(1);
		List<Integer> keys1 = new ArrayList<>();
		keys1.add(2);
		List<Integer> keys2 = new ArrayList<>();
		keys2.add(3);
		List<Integer> keys3 = new ArrayList<>();
		
		rooms.add(keys0);
		rooms.add(keys1);
		rooms.add(keys2);
		rooms.add(keys3);
		
		System.out.println(canVisitAllRooms(rooms));
	}
    private static boolean canVisitAllRooms(List<List<Integer>> rooms) {
		//用棧存儲下一步要參觀的房間
		Stack<Integer> dfs = new Stack<>(); 
		dfs.add(0);
		//用hashset存儲已經參觀過的房間
        HashSet<Integer> seen = new HashSet<Integer>(); 
        seen.add(0);
        while (!dfs.isEmpty()) {
            int i = dfs.pop();
            for (int j : rooms.get(i))
                if (!seen.contains(j)) {
                    dfs.add(j);
                    seen.add(j);
                    if (rooms.size() == seen.size()) return true;
                }
        }
        return rooms.size() == seen.size();
	}
	
}