【C++】競程筆記（DFS：深度優先搜尋）

程式碼範例參考：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，必須試其他位置。

回溯邏輯

void solve(int row, vector<int> &queens, vector<string> &solutions)

如果 row == 8，表示八個皇后都放好了 → 收集這個解。

否則就從第 $0$ 行到第 $7$ 行一個個試，直到成功為止。

每次放下一層（下一列）時，就遞迴往下走。

若沒成功，回到上一層試下一個可能點（回溯法）。

範例程式碼

#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 平移）。

首先剪掉同一行被佔用的情形：

if (!cols[col])

比對沒有剪枝的程式碼，光是這行就省略了從 row = 0 到 row = row - 1 的遍歷檢查，從 $O(n)$ 降至 $O(1)$ 。

其實對角線的做法也跟上面的一樣，因為我們都用了陣列去紀錄哪些皇后佔了什麼位置，所以可直接用一行判斷去解決：

if (!diag1[row + col])

if (!diag2[row - col + 7])

剪枝後的程式碼

#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. 迷宮矩陣

vector<string> maze;  // 大小為 n×n，maze[i][j] = '#' 或 '.'

1. 標記陣列

bool visited[105][105] = {false};
// visited[i][j] = true：代表 (i,j) 目前已在路徑上，不能重複走

1. 方向向量

int dx[4] = {-1, 1, 0, 0};  // 上、下、左、右 (Up, Down, Left, Right)
int dy[4] = { 0, 0,-1, 1};

1. 最短步數變數

int ans = INT_MAX;  // 如果設成 0 就會有誤差情形，因為題目是求最短路徑長

演算流程：

1. 一開始先判斷「若起點或終點任一為 #，則立刻輸出 No solution!」，結束程式。
2. 呼叫 DFS 函數 + 回溯（Backtracking）

visited[1][1] = true;        // 標記起點
dfs(1, 1, 1);                 // 從 (1,1) 出發，已走步數 steps = 1

咦？不是從 $(2, 2)$ 開始嗎？這是因為程式中的陣列都是從 $0$ 開始，所以 $(1, 1)$ 就等同 $(2, 2)$ 。

1. DFS 內部函數細節：

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（廣度優先搜尋）來做這題（請見下一篇筆記講解）。

#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 作為下一層的起點，確保不重複，也維持順序。

範例程式碼：

#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，並將三個用來記錄的陣列標記為已用：

       grid[r][c] = '0'+d;
       rowUsed[r][d] = colUsed[c][d] = blockUsed[b][d] = true;

填完後，就直接遞迴呼叫 dfs(pos+1)，往下一個空格移動。

1. 回溯機制：
   • 如果遞迴回傳 true，表示「下一層已經成功找到一組完整解」，一路往上直接 return true，就不要再試更大的 d 了，因為題目這邊要求輸出字典序最小的一組解。
   • 若 1~9 全部填過都不行的話，就要還原：

     rowUsed[r][d] = colUsed[c][d] = blockUsed[b][d] = false;
     grid[r][c] = '.';

然後回到上一層，嘗試上一格的下一個數字。

1. 終止條件：

   • 當 pos == empties.size()，代表所有空格都已成功填入，就馬上 return true，觸發整個搜尋樹的「捷徑返回」，然後再印出這 81 個字元的解。

2. 無解判定：

   • 若一開始判斷就發現違規的話，或整個 DFS 搜尋完都沒找到可以填的地方，就 return false，輸出 No solution.。

範例程式碼：

#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 的次數，即為油礦總數。

範例程式碼：

#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] 陣列來標記是否走過。

1. 用 DFS 搜尋一整塊的 JIZZ

流程如下：

• 遍歷整張地圖
• 每當遇到 ‘J’ 而且還沒被走過：
  • 認定這是一塊新 JIZZ（連通塊）。
  • 進行 DFS 探索整塊 JIZZ，計算其面積。
  • 更新連通塊數量、最大面積。

1. 輸出總連通塊數、最大的 JIZZ 面積

#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;
}