【C++】競程筆記（DFS：深度優先搜尋）
===
[TOC]
程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。
DFS 的前菜：八皇后問題
---
Problem : https://zerojudge.tw/ShowProblem?problemid=i644
這題可以透過窮舉法+遞迴（回溯法：Backtracking）的方式去解。
回溯法就是窮舉+遞迴，遇到不可能或失敗的情況後會回退一步，嘗試其他可能的解，直到找到解或全部演算完畢。
八皇后問題的目標是：
在 $8 \times 8$ 的棋盤上放置 $8$ 個皇后，使得任意兩個皇后不會互相攻擊，也就是說：
- 任意兩個皇后不在同一列（row）
- 任意兩個皇后不在同一行（column）
- 任意兩個皇后不在同一條對角線（diagonal）
至於為什麼是這樣？可以參考這篇西洋棋規則：https://blog.udn.com/puzzlez/4342425
### 解法
由於每列只能放一個皇后，因此可以將問題簡化為每一列放在哪一行。
在這邊開一個陣列 `queens[8]` 表示整個棋盤，`queens[i] = j` 表示第 `i` 列的皇后放在第 `j` 行。
#### 邏輯判定
每次遞迴放一個皇后，然後對目前位置去做衝突判定（isValid）：
- 對於目前第 `row` 列、欲擺在第 `col` 行，檢查：
- 是否有其他皇后也在 `col` 行 → 同行衝突。
- 是否有其他皇后在相同的對角線上：
- 左上到右下：`(r1 - r2) == (c1 - c2)`。
- 左下到右上：`(r1 - r2) == -(c1 - c2)`。
- 上述兩項可縮短成 `abs(r1 - r2) == abs(c1 - c2)` 方便計算。
只要有一項衝突，就不能擺這個位置，回傳 `false`，必須試其他位置。
#### 回溯邏輯
```cpp=
void solve(int row, vector<int> &queens, vector<string> &solutions)
```
如果 `row == 8`，表示八個皇后都放好了 → 收集這個解。
否則就從第 $0$ 行到第 $7$ 行一個個試，直到成功為止。
每次放下一層（下一列）時，就遞迴往下走。
若沒成功，回到上一層試下一個可能點（回溯法）。
### 範例程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;
bool isValid(const vector<int> &queens, int row, int col) {
for (int prevRow = 0; prevRow < row; ++prevRow) {
int prevCol = queens[prevRow];
if (prevCol == col || abs(prevCol - col) == abs(prevRow - row)) {
return false;
}
}
return true;
}
void solve(int row, vector<int> &queens, vector<string> &solutions) {
if (row == 8) { // 8 列都成功放置的話，表示找到一組解
string solution;
for (int col : queens) {
solution += to_string(col + 1); // 轉為從 1 開始的列號
}
solutions.push_back(solution);
return;
}
// 嘗試第 row 列的每一行
// 若該行可放，就放皇后，然後遞迴處理下一列
for (int col = 0; col < 8; ++col) {
if (isValid(queens, row, col)) {
queens[row] = col;
solve(row + 1, queens, solutions);
}
}
}
int main() {
vector<string> solutions;
vector<int> queens(8); // 第 i 列皇后擺放在第 queens[i] 行（從 0 開始）
solve(0, queens, solutions);
sort(solutions.begin(), solutions.end()); // 按照字典序排序
for (int i = 0; i < solutions.size(); ++i) {
cout << (i + 1) << ": " << solutions[i] << endl;
}
return 0;
}
```
### 剪枝（Pruning）
剪枝（Pruning）是一種在搜尋或遞迴演算法中的優化技巧，目的在於提前排除不可能得到有效解的分支，以減少不必要的計算，提升效率。
回溯法就算是一種暴力法，透過剪枝可以優化他，少走冤枉路。
白話一點：剪枝就是當我們發現可能走在一條完全錯誤的路上時，那就應該要放棄這條，走別條。
來細講一下要怎麼對八皇后問題做剪枝吧：
這邊首先用三個 bool 陣列來記錄哪些位置已被皇后佔用：
`cols[8]`：記錄某一欄是否已有皇后。
`diag1[15]`：主對角線（↘），對應 `row + col`。
`diag2[15]`：副對角線（↙），對應 `row - col + 7`（可能有負值，需 `+7` 平移）。
首先剪掉同一行被佔用的情形：
```cpp
if (!cols[col])
```
比對沒有剪枝的程式碼，光是這行就省略了從 `row = 0` 到 `row = row - 1` 的遍歷檢查，從 $O(n)$ 降至 $O(1)$ 。
其實對角線的做法也跟上面的一樣，因為我們都用了陣列去紀錄哪些皇后佔了什麼位置，所以可直接用一行判斷去解決：
```cpp
if (!diag1[row + col])
```
```cpp
if (!diag2[row - col + 7])
```
### 剪枝後的程式碼
```cpp=
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string> solutions;
int queens[8];
bool cols[8] = {false};
bool diag1[15] = {false}; // ↘ 對角線 (row + col)
bool diag2[15] = {false}; // ↙ 對角線 (row - col + 7)
void solve(int row) {
if (row == 8) {
string s;
for (int i = 0; i < 8; ++i) {
s += to_string(queens[i] + 1); // 行號從 1 開始
}
solutions.push_back(s);
return;
}
for (int col = 0; col < 8; ++col) {
if (!cols[col] && !diag1[row + col] && !diag2[row - col + 7]) {
// 放置皇后
queens[row] = col;
cols[col] = diag1[row + col] = diag2[row - col + 7] = true;
solve(row + 1);
// 回溯
cols[col] = diag1[row + col] = diag2[row - col + 7] = false;
}
}
}
int main() {
solve(0);
sort(solutions.begin(), solutions.end());
for (int i = 0; i < solutions.size(); ++i) {
cout << (i + 1) << ": " << solutions[i] << endl;
}
return 0;
}
```
深度優先搜尋（Depth Fisrt Search, DFS）
---
DFS 是啥？能吃嗎？請看以下這張圖：
Image Source：https://zh-yue.wikipedia.org/wiki/File:Depth-First-Search.gif
DFS 是遍歷或搜尋樹或圖的演算法。
其實跟回溯法有點像，但有點不一樣是 DFS 會探到底，如果走到不能走了，再回到起點，繼續走別條路試試看。
有兩種實作 DFS 的方式：
1. 遞迴（Recursive）
2. 堆疊（stack）
普遍使用遞迴，因為你用堆疊你也是一樣在模擬遞迴，還不如用遞迴。
### 範例：走迷宮
Problem : https://zerojudge.tw/ShowProblem?problemid=a982
題目敘述：
給定一個 $n \times n$ 格的迷宮，迷宮中 `#` 代表障礙物，`.` 代表一般的路，玩家固定於 $(2, 2)$ 出發，目的地為 $(n-1, n-1)$ ，求包括起點和終點，最少路徑的長度。
輸入說明：
$N \leq 100$ 。
$N$ 行 $N$ 列由 `#` 和 `.` 組成的迷宮。
輸出說明：
一個正整數，代表最短路徑的長度，如果不可能到達終點，則印出 `No solution!`
範例輸入：
```
9
#########
#.......#
#.#####.#
#.......#
##.#.####
#..#.#..#
#.##.##.#
#.......#
#########
```
範例輸出：
```
13
```
#### 解題思路
準備幾個資料結構：
1. 迷宮矩陣
```cpp
vector<string> maze; // 大小為 n×n，maze[i][j] = '#' 或 '.'
```
2. 標記陣列
```cpp
bool visited[105][105] = {false};
// visited[i][j] = true：代表 (i,j) 目前已在路徑上，不能重複走
```
3. 方向向量
```cpp
int dx[4] = {-1, 1, 0, 0}; // 上、下、左、右 (Up, Down, Left, Right)
int dy[4] = { 0, 0,-1, 1};
```
4. 最短步數變數
```cpp
int ans = INT_MAX; // 如果設成 0 就會有誤差情形，因為題目是求最短路徑長
```
演算流程：
1. 一開始先判斷「若起點或終點任一為 `#`，則立刻輸出 `No solution!`」，結束程式。
2. 呼叫 DFS 函數 + 回溯（Backtracking）
```cpp
visited[1][1] = true; // 標記起點
dfs(1, 1, 1); // 從 (1,1) 出發，已走步數 steps = 1
```
咦？不是從 $(2, 2)$ 開始嗎？這是因為程式中的陣列都是從 $0$ 開始，所以 $(1, 1)$ 就等同 $(2, 2)$ 。
3. DFS 內部函數細節：
```cpp=
void dfs(int x, int y, int steps) {
// (1) 剪枝：若當前步數已不可能比現有 ans 更短，就不必繼續探索
if (steps >= ans) return;
// (2) 檢查是否到達終點
if (x == n-2 && y == n-2) {
ans = steps; // 更新最短步數
return;
}
// (3) 四個方向遞迴嘗試
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
// 檢查：在邊界內、不是障礙、且未走訪
if (nx >= 0 && nx < n && ny >= 0 && ny < n
&& maze[nx][ny] == '.' && !visited[nx][ny]) {
// 標記並深入
visited[nx][ny] = true;
dfs(nx, ny, steps + 1);
// 回溯：恢復未走訪狀態
visited[nx][ny] = false;
}
}
}
```
### 完整程式碼
使用 DFS 方法 submit 過後，會發現有個測資點 TLE，這是因為 DFS 不適合拿來求最短路徑，效率太差了。
所以這時候就要改用 BFS（廣度優先搜尋）來做這題（請見下一篇筆記講解）。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n;
vector<string> maze;
bool visited[105][105];
int ans = INT_MAX;
// 四個移動方向：上、下、左、右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
// DFS 函式：從 (x,y) 出發，已走 steps 步
void dfs(int x, int y, int steps) {
// 如果已超過目前最短，剪枝
if (steps >= ans) return;
// 到達終點 (n-2,n-2)
if (x == n-2 && y == n-2) {
ans = steps;
return;
}
// 嘗試四個方向
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
// 邊界檢查 & 障礙物 & 是否已走訪
if (nx >= 0 && nx < n && ny >= 0 && ny < n
&& !visited[nx][ny] && maze[nx][ny] == '.') {
visited[nx][ny] = true;
dfs(nx, ny, steps + 1);
visited[nx][ny] = false; // 回溯
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
maze.resize(n);
for (int i = 0; i < n; ++i) {
cin >> maze[i];
}
// 起點 (1,1) 或終點 (n-2,n-2) 若為障礙，直接無解
if (maze[1][1] == '#' || maze[n-2][n-2] == '#') {
cout << "No solution!\n";
return 0;
}
visited[1][1] = true;
dfs(1, 1, 1); // 包含起點步數從 1 開始算
if (ans == INT_MAX) {
cout << "No solution!\n";
} else {
cout << ans << "\n";
}
return 0;
}
```
習題練習
---
### 1. Lotto
Problem : https://tioj.sprout.tw/problems/61
這題就是組合（Combination）問題，給你一個 $k$ 且 $k > 6$ ，並且求出 $C(k, 6)$ 的所有可能組合。
解題思路：
設計 dfs 遞迴函數，共四個參數，numbers 表示輸入的已排序集合，comb 為所有可能的組合之集合，index 為在 numbers 中下個可選擇的起始位置，depth 為目前已選多少數字（depth 0 ~ 5）。
終止條件：
`depth == 6` 時終止條件，表示 comb 裡面的數字滿了，並依序輸出這些可能的組合，再進行回溯。
遞迴選擇：
```
// pseudo code
for i = index … k-1:
comb[depth] = numbers[i];
dfs(numbers, comb, i+1, depth+1);
```
每次從 `i = index` 開始選一個新數字，放入 `comb[depth]`，再遞迴挑下一個。
`i+1` 作為下一層的起點，確保不重複，也維持順序。
範例程式碼：
```cpp=
#include <bits/stdc++.h>
using namespace std;
// 遞迴函數：用來窮舉所有 C(k, 6) 的組合
// 參數說明：
// numbers：目前的 Lucky Number 集合（已排序）
// comb：當前正在組合的 6 個數字暫存陣列
// index：下一個可選的起始位置（確保組合不重複）
// depth：目前 comb 中已經選了幾個數（從 0 ~ 6）
void dfs(const vector<int>& numbers, vector<int>& comb, int index, int depth){
// 遞迴終止條件：當選滿 6 個數字時，印出目前這組組合
if (depth == 6){
for (int i = 0; i < 6; ++i){
if (i > 0) cout << " ";
cout << comb[i];
}
cout << endl;
return; // 回傳到上一層遞迴
}
int n = numbers.size();
// 遍歷所有剩下可以選的數字
for (int i = index; i < n; ++i){
comb[depth] = numbers[i];
dfs(numbers, comb, i + 1, depth + 1); // 遞迴處理下一層
// 這邊無需手動清除 comb[depth]，因為會被下一輪覆蓋，就是上上面那行程式碼
}
}
int main(){
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--){
int k;
cin >> k;
vector <int> numbers(k);
for (int i = 0; i < k; ++i){
cin >> numbers[i];
}
vector <int> comb(6);
dfs(numbers, comb, 0, 0);
}
return 0;
}
```
### 2. 數獨
Problem : https://tioj.sprout.tw/problems/60
數獨的規則是在每一行、每一列、每個子矩陣中都不能出現相同的數字，一般的數獨都是給 $9 \times 9$ 的方格，以九宮格的形式進行數獨遊戲。
具體玩法可參考：https://sudoku.com/tw/shu-du-gui-ze/
解題思路：
首先每筆測資會收到 81 個字元，代表這個 $9 \times 9$ 方格的初始佈局。
先檢查「已填數字」有無違規。若同一行（col）、同一列（row）或同一 $3 \times 3$ 九宮格內，同樣的數字重複出現，就直接判定「No solution!」。
再來是一些資料結構上的初始化設定：
- 格子狀態：用 `grid[r][c]` 存放第 `r` 行、第 `c` 列的字元（`'.'` 或 `'1'~'9'`）。
- `rowUsed[r][d]`：第 `r` 行是否已經用過數字 `d`？
- `colUsed[c][d]`：第 `c` 列是否已經用過數字 `d`？
- `blockUsed[b][d]`：第 `b` 號 $3 \times 3$ 宮格是否已經用過數字 `d`？
然後把所有 `'.'` 的格子位置依序存進一個陣列 `empties`。
演算法流程（DFS+回溯法）：
1. 填上第一個空格（`empties[0]`）
- 對應 `empties[0]`，在第 `r` 行、第 `c` 列、第 `b` 宮格。
- 嘗試數字 `d = 1,2,3…9`：
- 若 `rowUsed[r][d] || colUsed[c][d] || blockUsed[b][d]` 運算式結果為 `true`，代表這已經違規了，就直接跳過 `d`。
- 否則，填入 `d`，並將三個用來記錄的陣列標記為已用：
```cpp=
grid[r][c] = '0'+d;
rowUsed[r][d] = colUsed[c][d] = blockUsed[b][d] = true;
```
填完後，就直接遞迴呼叫 `dfs(pos+1)`，往下一個空格移動。
2. 回溯機制：
- 如果遞迴回傳 `true`，表示「下一層已經成功找到一組完整解」，一路往上直接 `return true`，就不要再試更大的 `d` 了，因為題目這邊要求輸出字典序最小的一組解。
- 若 1~9 全部填過都不行的話，就要還原：
```cpp=
rowUsed[r][d] = colUsed[c][d] = blockUsed[b][d] = false;
grid[r][c] = '.';
```
然後回到上一層，嘗試上一格的下一個數字。
3. 終止條件：
- 當 `pos == empties.size()`，代表所有空格都已成功填入，就馬上 `return true`，觸發整個搜尋樹的「捷徑返回」，然後再印出這 81 個字元的解。
4. 無解判定：
- 若一開始判斷就發現違規的話，或整個 DFS 搜尋完都沒找到可以填的地方，就 `return false`，輸出 `No solution.`。
範例程式碼：
```cpp=
#include <bits/stdc++.h>
using namespace std;
int T; // 測試資料組數
string s; // 單筆輸入的 81 字元字串（'.' 或 '1'~'9'）
char grid[9][9]; // 轉換後的 9×9 方陣
// 三個布林陣列用來標記：某行、某列、某 3×3 宮格 是否已經使用過 某個數字 d
bool rowUsed[9][10], colUsed[9][10], blockUsed[9][10];
// 用來存所有空格（未填位置）的線性索引（0~80），深度優先搜尋時依序填入
vector<int> empties;
/**
* 深度優先搜尋 + 回溯 (DFS + Backtracking)
* pos：目前要填入 empties[pos] 這個空格
* 回傳值：若從此狀態能找到合法解，回傳 true；否則 false
*/
bool dfs(int pos) {
// 終止條件：所有空格都已填完
if (pos == (int)empties.size()) {
return true; // 找到一組完整合法解，沿呼叫鏈一路回傳 true
}
int idx = empties[pos]; // 取得第 pos 號空格在 0~80 的線性編號
int r = idx / 9; // 換算出所在的「行」（row）
int c = idx % 9; // 換算出所在的「列」（column）
int b = (r/3)*3 + (c/3); // 計算所屬的第 b 號 3×3 宮格
// 試從最小數字 1 開始，一直到 9
for (int d = 1; d <= 9; ++d) {
// 如果此數字在行、列或九宮格中已被使用，則跳過（剪枝）
if (rowUsed[r][d] || colUsed[c][d] || blockUsed[b][d]) {
continue;
}
// 標記「填入」動作：更新 grid，並標示該行、列已被用過
grid[r][c] = char('0' + d);
rowUsed[r][d] = true;
colUsed[c][d] = true;
blockUsed[b][d] = true;
// 試填下一個空格；若回傳 true，表示已經找到最小字典序解
if (dfs(pos + 1)) {
return true; // 不再試更大的 d
}
// 回溯還原
rowUsed[r][d] = false;
colUsed[c][d] = false;
blockUsed[b][d] = false;
grid[r][c] = '.';
}
// 1~9 都試過仍無解，回傳 false 給上一層繼續嘗試其他數字
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--) {
cin >> s;
empties.clear();
// memset 是 <cstring> 的函數
// 用於填入布林陣列值可行，但整數的不行，因為 memset 是在 byte 層次上運算的
memset(rowUsed, 0, sizeof(rowUsed));
memset(colUsed, 0, sizeof(colUsed));
memset(blockUsed, 0, sizeof(blockUsed));
bool invalid = false; // 檢查初始已填數字是否違規
for (int i = 0; i < 81; ++i) {
int r = i / 9, c = i % 9;
int b = (r/3)*3 + (c/3);
char ch = s[i];
grid[r][c] = ch;
if (ch == '.') {
// 收集空格索引，之後用 DFS 依序填入
empties.push_back(i);
} else {
// 已填入的數字，計算對應整數值
int d = ch - '0';
// 如果已經在行、列或九宮格中被用過，則直接標示為「無解」
if (rowUsed[r][d] || colUsed[c][d] || blockUsed[b][d]) {
invalid = true;
} else {
// 否則將其標記為已用
rowUsed[r][d] = true;
colUsed[c][d] = true;
blockUsed[b][d] = true;
}
}
}
if (invalid || !dfs(0)) {
cout << "No solution.\n";
} else {
// 走到這裡表示 grid 已經被完整填入一組字典序最小解
// 按行列順序連續輸出 81 字元
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
cout << grid[r][c];
}
}
cout << "\n";
}
}
return 0;
}
```
### 3. UVa 572 - Oil Deposits
Problem : https://zerojudge.tw/ShowProblem?problemid=c129
若兩個 `@` 在 8 個方向上彼此相鄰，就視為一整塊油礦（Oil Deposit）。
而相鄰定義與踩地雷遊戲相同的意思是：
上下左右（4 個方向）：
- ↑、↓、←、→
對角線（4 個方向）：
- ↖、↗、↙、↘
座標偏移表：
| 方向 | dx | dy | 說明 |
| -- | -- | -- | -- |
| ↖ | -1 | -1 | 左上 |
| ↑ | -1 | 0 | 上 |
| ↗ | -1 | +1 | 右上 |
| ← | 0 | -1 | 左 |
| → | 0 | +1 | 右 |
| ↙ | +1 | -1 | 左下 |
| ↓ | +1 | 0 | 下 |
| ↘ | +1 | +1 | 右下 |
只要有任兩個 `@` 與上述八個方向相連起來，就是一個 oil deposit。
而目標是要找出有多少個不一樣的 oil deposit。
解題思路：
1. 遍歷整張地圖
2. 若遇到一個還沒處理過的 `@`，就從該格出發，做一次 DFS，然後把所有與它相連的 `@` 都標記為「已訪問」。
3. 每一次 DFS，就代表發現一塊新的油礦。因為這些 `@` 沒跟之前的任何油礦連在一起。
4. 統計做 DFS 的次數，即為油礦總數。
範例程式碼：
```cpp=
#include <bits/stdc++.h>
using namespace std;
// 定義 8 個方向的移動向量（上下左右 + 四個斜角方向）
const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; // 對應 x（row）方向
const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; // 對應 y（col）方向
int m, n; // 地圖的列數與行數
vector<string> grid; // 儲存地圖（每列為一個字串）
vector<vector<bool>> visited; // 記錄每個格子是否已被訪問
// dfs：從 (x, y) 開始，把所有連通的 '@' 都標記為已訪問
void dfs(int x, int y) {
visited[x][y] = true; // 標記目前格子為已訪問
// 試往 8 個方向移動
for (int dir = 0; dir < 8; ++dir) {
int nx = x + dx[dir]; // 計算新位置 x
int ny = y + dy[dir]; // 計算新位置 y
// 確保新位置在地圖範圍內
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (!visited[nx][ny] && grid[nx][ny] == '@') {
dfs(nx, ny); // 遞迴繼續搜尋
}
}
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
while (cin >> m >> n && (m != 0 || n != 0)) {
// 註：assign() 等同賦值，但比一般的 = 等號賦值更靈活
grid.assign(m, ""); // 初始化地圖大小 m 行
visited.assign(m, vector<bool>(n, false)); // 初始化訪問狀態矩陣
for (int i = 0; i < m; ++i) {
cin >> grid[i];
}
int oilDeposits = 0; // 統計油礦區的數量
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 若當前格子是 '@' 且未被訪問
if (!visited[i][j] && grid[i][j] == '@') {
dfs(i, j); // 從這格開始 DFS 掃描整個油礦
++oilDeposits; // 成功找到一個新的 oil deposit
}
}
}
cout << oilDeposits << '\n';
}
return 0;
}
```
### 4. 祖靈被榨乾了!!!!!!!!
Problem : https://zerojudge.tw/ShowProblem?problemid=a597
基本上就是跟前面一樣的套路，只是稍微改一下而已。
解題思路：
1.
首先輸入 m, n（行列數），
建立 `grid[m][n]` 陣列儲存圖形資訊；
建立 `visited[m][n]` 陣列來標記是否走過。
2. 用 DFS 搜尋一整塊的 JIZZ
流程如下：
- 遍歷整張地圖
- 每當遇到 'J' 而且還沒被走過：
- 認定這是一塊新 JIZZ（連通塊）。
- 進行 DFS 探索整塊 JIZZ，計算其面積。
- 更新連通塊數量、最大面積。
3. 輸出總連通塊數、最大的 JIZZ 面積
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int MAX = 505; // 最大行列數（題目上限為 500）
int m, n; // 行、列數
char grid[MAX][MAX]; // 儲存輸入的棋盤，每格為 'X' 或 'J'
bool visited[MAX][MAX]; // 記錄每格是否已經被 DFS 探索過
// 四個方向：上、下、左、右（四方位）
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
// dfs 探索整個連通區塊，並回傳該區塊的面積
int dfs(int x, int y) {
visited[x][y] = true; // 標記目前格子已被訪問
int area = 1; // 記錄目前這塊的面積（從這格開始算）
// 探索四個方向
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir]; // 下一格的 x 座標
int ny = y + dy[dir]; // 下一格的 y 座標
// 檢查是否在邊界內，且下一格為 'J' 且尚未走訪
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
grid[nx][ny] == 'J' && !visited[nx][ny]) {
area += dfs(nx, ny); // 遞迴探索下一格，並累加面積
}
}
return area;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> m >> n) {
for (int i = 0; i < m; ++i) {
cin >> grid[i]; // 每行輸入一整串字元（無空白）
}
// 初始化 visited 陣列為 false
for (int i = 0; i < m; ++i)
fill(visited[i], visited[i] + n, false);
int count = 0; // JIZZ 的連通塊數量
int max_area = 0; // 最大 JIZZ 連通塊的面積
// 遍歷整張地圖
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 若此格為 'J' 且尚未被走訪
if (grid[i][j] == 'J' && !visited[i][j]) {
int area = dfs(i, j);
count++; // 新的一塊 JIZZ，數量 + 1
max_area = max(max_area, area); // 更新最大面積
}
}
}
cout << count << " " << max_area << "\n";
}
return 0;
}
```
Sign in with Wallet
Connect another wallet