ข้อสอบท้ายค่าย 2 ปีการศึกษา 2566 ศูนย์ สอวน. มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี ข้อ Largest Island

---

Author: Nagorn Phongphasura

---

Problem

สรุปโจทย์

มีพื้นที่ขนาด \(N \times M\) โดยแต่ละช่องจะเป็น:

• อักขระ '0' คือ พื้นน้ำ
• อักขระ '1' คือ พื้นเกาะ

โดยพื้นดินในเกาะ จะต้องติดกับพื้นดินในเกาะเดียวกันอย่างน้อย 1 ใน 4 ทิศทาง ได้แก่ บน ล่าง ซ้าย และขวา

สิ่งที่ต้องทำ

หาขนาดของเกาะที่ใหญ่ที่สุด ในพื้นที่ที่กำหนดมาให้

Constraints

\(2 \leq N,M \leq 170\)

Prerequisites

• DFS/BFS

---

Solution

วิธีทำ

เราสามารถมองโจทย์ข้อนี้เป็น Graph ได้ โดยมองแต่ละช่องในตารางเป็น Node และทิศทางทั้ง 4 ทิศที่ติดกับแต่ละช่องเป็น Edge

ดังนั้น ขั้นตอนการแก้โจทย์ข้อนี้ ก็คือ:

1. Loop \(i\) ตั้งแต่ \(0\) -> \(n - 1\) และ Loop \(j\) ตั้งแต่ \(0\) -> \(m - 1\)
2. หากพื้นที่ที่กำลังตรวจสอบ เป็นพื้นที่เกาะ ให้ DFS/BFS เข้าไป โดยเงื่อนไขในการ DFS/BFS ของเราคือ จะไม่วนซ้ำพื้นที่ที่เคยตรวจสอบมาแล้ว และจะท่องเข้าไปแค่พื้นที่ที่เป็นเกาะ
3. แต่ละรอบที่เราวน DFS/BFS เราจะสร้างตัวแปร \(cnt\) ขึ้นมา เพื่อนับพื้นที่เกาะที่กำลังท่องอยู่
4. Loop ตามทิศทางทั้ง 4 (บน ล่าง ซ้าย ขวา) เพื่อใส่ช่องใหม่เข้าไปใน Data Structure ที่ใช้ในการ DFS/BFS
5. เก็บขนาดพื้นที่ที่ใหญ่ที่สุดที่เคยตรวจสอบมาในตัวเเปร \(ans\)

สามารถมองภาพง่ายๆ โดยลองพิจารณาว่า:

1. เราจะหาจุดเริ่มต้นการตรวจสอบเกาะแต่ละเกาะ
2. ท่องเข้าไปในเกาะนั้น โดยให้การ "Loop" เป็นการ "เดิน" ในเกาะ
3. เดิน 4 ทิศทาง และแต่ละช่องที่เดิน เราจะ Mark เอาไว้ว่า เคยไปมาแล้วหรือไม่ โดยถ้าหากว่าใน 4 ทิศทางที่เรา Loop เราพบช่องที่เคยเดินมาแล้ว หรือช่องที่เป็นพื้นน้ำ เราก็ไม่จำเป็นต้องเดินไปทางนั้นแล้ว

---

Code:

c2_kmutt_66_largest_island.cpp

#include <bits/stdc++.h>
#define int long long

using namespace std;

int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);

    // input
    int n, m;
    cin >> n >> m;
    vector <vector <char>> a(n, vector <char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    int ans = 0; // ตัวแปรที่ทำหน้าที่เก็บขนาดเกาะที่ใหญ่ที่สุดที่เคยตรวจสอบมา

    // visited: เก็บว่าช่องที่ i, j เคยวนมาแล้วหรือยัง
    vector <vector <bool>> visited(n, vector <bool>(m, false));
    // d_ : เก็บทิศทาง แกน x และ แกน y
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    // loop i = 0 -> n, j = 0 -> m
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // ตรวจสอบว่าเป็นพื้นเกาะ และยังไม่ได้ตรวจสอบ
            if (!visited[i][j] && a[i][j] == '1') {
                visited[i][j] = true; // ตั้งเป็นตรวจสอบแล้ว
                queue<pair<int, int>> q; // queue ใช้ BFS
                q.push({i, j});
                int cnt = 1; // cnt ใช้นับพื้นที่เกาะปัจจุบัน

                while (!q.empty()) {
                    auto [x, y] = q.front(); // ดึงตำแหน่งปัจจุบันออกมาจาก queue
                    q.pop();

                    // Loop 4 ทิศทาง
                    for (int k = 0; k < 4; k++) {
                        // ตำแหน่งใหม่หากเดินไปตามทิศทางนั้นๆ
                        int nx = x + dx[k];
                        int ny = y + dy[k];

                        // ตรวจสอบว่า:
                        // 1. อยู่ในอาณาเขตหรือไม่
                        // 2. เป็นพื้นเกาะหรือไม่
                        // 3. เคยตรวจสอบแล้วหรือไม่
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if (visited[nx][ny] || a[nx][ny] == '0') continue;

                        visited[nx][ny] = true; // ตั้งว่าเคยตรวจสอบแล้ว
                        q.push({nx, ny}); // ใส่เข้า queue
                        cnt++;
                    }
                }

                ans = max(ans, cnt); // ปรับค่า ans ว่า เกาะปัจจุบัน มีขนาดใหญ่กว่าเกาะที่ใหญ่ที่สุดที่เคยตรวจสอบมาหรือไม่
            }
        }
    }

    // Output
    cout << ans;
    return 0;
}

Total Time Complexity

\(O(nm)\)