給個玩具
先備知識
queue用法

BFS

圖的走訪

給定一張圖，要怎麼樣歷遍所有點或找尋兩點路徑?

$\mathrm{範}\mathrm{例}\mathrm{由}1\mathrm{開}\mathrm{始}\mathrm{至}4$

我們可以由

$1$ 號點開始，每次走訪該點附近尚未走訪的點
並將走訪過的點丟入一個

$Queue$ 裡面
如此反覆循環，直至走到目標點為止

時間複雜度：

$O(E)$

$E$ 為圖的點數，一次歷遍

走訪小技巧
開一個

$vis$ 陣列，將走訪過的點標記
避免再次尋訪浪費時間
(視題目做標記)

vis[100005] = {};
vis[i] = 1; //代表一號點走過

迷宮問題

請先看 Zero Judge d453

$000000$

$011101$

$000010$

$011000$

$000010$

起點在第一行第三列 (直行橫列)
因為

$a[3][1]$
同理終點第四行第三列

我們可以建一個陣列，表示走路方向

// version 1
int dir[4][2] = {
    {0,1},
    {1,0},
    {0,-1},
    {-1,0},
};
// version 2
int dx[5] = {0,1,0,-1};
int dy[5] = {1,0,-1,0};

然後針對當前座標
找尋他四周可不可以走，如果可以就一直走訪
然後丟入

$Queue$
直至終點或無法走尋

同剛剛的問題，不過這裡一定要標記!
作法如下

bool vis[1005][1005];
vis[3][1] = 1; //表示$(3,1)走訪過$

BFS題目

• CSES Message Route
• CSES Counting Room
• Zero Judge d453
• TIOJ 2208
• TIOJ 2180

難度自上排下，TIOJ 2180需要 Priority Queue

DFS

圖的走訪

給定一張圖，要怎麼樣歷遍所有點或找尋兩點路徑?

$\mathrm{範}\mathrm{例}\mathrm{由}1\mathrm{開}\mathrm{始}\mathrm{至}4$

我們可以由

$1$ 號點開始，一直走，走到不能走為止
以圖為例，先從

$1$號點開始
往二號，三號，五號，再到四號
到底後返回五號
再走至六號

時間複雜度：

$O(E)$

$E$ 為圖的點數，一次歷遍

走訪小技巧
開一個

$vis$ 陣列，將走訪過的點標記
避免再次尋訪浪費時間
(視題目做標記)

vis[100005] = {};
vis[i] = 1; //代表一號點走過

DFS題目

• Zero Judge c463
• Code Force 218C
• TIOJ 1420