# DFS
# 想法
深度優先搜尋法（Depth-First Search）是一種樹（Tree）或圖（Graph）資料結構的搜索演算法，從圖的某一節點 (vertex, node) 開始走訪，盡可能最深入到分支深處再回溯其他節點。可應用於有向圖與無向圖的搜尋。
# 動圖演示
# 方法
運用遞迴的方式，不斷的往合理的狀況往下探索，直到無法在往下探索後返回，直到把所有狀況都跑過一遍，有時需要用到 stack 去幫忙輔助。
# 用途
用於拓撲排序，解決需要圖形回溯的問題，檢測圖形中的循環，查找兩個節點之間的所有路徑等。當然，還有很多喔～～
# 基本例題
c129: 00572 - Oil Deposits
# 內容
找出這塊地包含幾個不同的 oil deposit。
# 思路
開兩個二維陣列，一個紀錄圖形，另一個紀錄是否有走過，如果有油且未走過總是就加一。
#include <iostream> | |
using namespace std; | |
int visited[100][100]={0}; | |
char mp[100][100]; | |
int r,c; | |
void dfs(int i,int j) { | |
if(i<0||i>=r||j<0||j>=c||visited[i][j]==1||mp[i][j]=='*') | |
return; | |
visited[i][j]=1; | |
dfs(i-1,j-1); | |
dfs(i-1,j); | |
dfs(i-1,j+1); | |
dfs(i,j-1); | |
dfs(i,j+1); | |
dfs(i+1,j-1); | |
dfs(i+1,j); | |
dfs(i+1,j+1); | |
} | |
int main(){ | |
while(cin >> r >> c && r>0 && c>0) { | |
int cnt=0; | |
for(int i=0;i<r;i++) | |
for(int j=0;j<c;j++) { | |
cin >> mp[i][j]; | |
visited[i][j]=0; | |
} | |
for(int i=0;i<r;i++){ | |
for(int j=0;j<c;j++){ | |
if(mp[i][j]=='@'&&visited[i][j]==0){ | |
dfs(i,j); | |
cnt++; | |
} | |
} | |
} | |
cout << cnt << endl; | |
} | |
return 0; | |
} |
a229: 括號匹配問題
# 內容簡述
請寫一個程式把所有合法括號匹配方式列出來！
合法匹配的括號，從答案列的開頭到答案列某一點，左括弧次數永遠大於等於右括弧！
# 解題思路
使用 DFS，如果途中 (>) 則直接 return ，直到放置數達到 2*n 為止
# 程式碼
#include <iostream> | |
using namespace std; | |
string s; int a, b; | |
void dfs(int n) { | |
if(a < b) return; | |
if(s.size() == n * 2) { if(a == b) cout << s << '\n'; } | |
else { | |
s.push_back('('); a ++; dfs(n); s.pop_back(); a--; | |
s.push_back(')'); b ++; dfs(n); s.pop_back(); b--; | |
} | |
} | |
int main() { | |
int n; while(cin >> n) dfs(n); | |
} |
;;;
