สำหรับข้อนี้ โจทย์ได้ให้พิกัดที่แต่ละคนนั่งมาเป็นที่เรียบร้อยแล้ว โดยพิกัดที่มีคนนั่งจะถูกแสดงด้วย "1" ดังนั้นหน้าที่ของเราคือเราต้องตรวจสอบว่ามีกลุ่มคนทั้งหมดกี่กลุ่ม (มี "1" ที่ติดกันทั้งหมดกี่กลุ่ม )

ขั้นตอนที่ 1 : เลือกวิธีการเก็บข้อมูล

เนื่องจากโจทย์ได้ให้เป็นตารางสี่เหลี่ยมที่ระบุว่าใครนั่งอยู่ที่ใดไว้แล้ว ดังนั้นวิธีที่ง่ายที่สุดคือสร้างอาเรย์สองมิติโดยมิติหนึ่งใช้อ้างอิงแถว ส่วนอีกมิติใช้อ้างอิงคอลั่มน์ เช่น

$\begin{matrix} 1 & 0\\ 0 & 1 \end{matrix}$

อาจกำหนดให้ arr[0][0]="1"

ขั้นตอนที่ 2 : ทำการตรวจสอบว่ามีกลุ่มคนทั้งหมดที่กลุ่ม

ซึ่งวิธีการทำขั้นตอนนี้ หากทำด้วยมือ ก็สามารถทำได้โดย ให้เราเลือกคนมาคนหนึ่ง แล้วทำสัญลักษณ์คนที่อยู่ในกลุ่มคนเดียวกับคนๆนั้น (อย่าลืมทำสัญลักษณ์ให้คนแรกด้วย) พอดำเนินการกับกลุ่มนี้เสร็จ ก็ให้ขีดเส้นลงกระดาษ 1 เส้นแสดงว่านับไปแล้ว 1 กลุ่ม แล้วเราก็ไปหาคนต่อไปที่เรายังไม่ได้ทำสัญลักษณ์ พอตอนสุดท้าย เราก็มานับจำนวนเส้นที่ขีดไว้แล้วจัดเตรียมไม้ขีดไฟเท่ากับจำนวนที่นับได้

เวลาเขียนโปรแกรมก็ใช้หลักการเดียวกับที่กล่าวมา ซึ่งตอนทำหาค้นหาคนที่อยู่ในกลุ่มเดียวกัน อาจทำการค้นหาในแนวกว้าง (แนว ๆ BFS) หรือทำการค้นหาในแนวลึก (แนว ๆ DFS) ก็ได้

คำแนะนำขั้นตอนการทำสัญลักษณ์ : อาจทำการสร้างอาเรย์สองมิติประเภท boolean เพิ่มอีก 1 อันเพื่อเก็บว่าคนๆนี้เรามาตรวจสอบแล้วหรือยัง เช่นถ้ากำหนดอาเรย์ตำแหน่งของคนได้ดังนี้

$\begin{matrix} 1 & 0\\ 0 & 1 \end{matrix}$

อาจสร้างอาเรย์อีกอันในลักษณะ

$\begin{matrix} FALSE & FALSE\\ FALSE & FALSE \end{matrix}$

ในตอนแรก (FALSE หมดเพราะยังไม่ได้ตรวจสอบใครทั้งสิ้น)

พอเริ่มทำการตรวจสอบ สมมติให้เริ่มที่คนพิกัด (0,0) เราก็จะเริ่มทำการเปลี่ยนค่าในอีกอาเรย์เป็น

$\begin{matrix} TRUE & FALSE\\ FALSE & FALSE \end{matrix}$

แสดงให้เห็นว่าเราทำสัญลักษณ์คนที่พิกัด (0,0) เป็นที่เรียบร้อยแล้ว

และเมื่อทำการเช็คคนที่อยู่รอบๆพิกัด (0,0) จะพบคนที่ (1,1) ด้วย เราจะเปลี่ยนค่าในอีกอาเรย์เป็น

$\begin{matrix} TRUE & FALSE\\ FALSE & TRUE \end{matrix}$

แสดงให้เห็นว่าเราทำสัญลักษณ์คนที่พิกัด (0,0) และ (1,1) เป็นที่เรียบร้อยแล้ว

และจากตัวอย่างนี้จะพบว่า เราได้เช็คครบทุกคนในตารางแล้ว ถือว่าจบการค้นหา ซึ่งสามารถสรุปได้ว่ามีกลุ่มคนทั้งหมดหนึ่งกลุ่ม ดังนั้นคำตอบของข้อมูลชุดนี้คือ 1

ในโค้ดตัวอย่างที่กำลังจะกล่าวในส่วนต่อไป

1. จะนำเสนอวิธีในการทำสัญลักษณ์โดยการปรับช่องที่ตรวจสอบแล้วจาก "1" เป็น "0" แทนการสร้างอีกอาเรย์มาเก็บสถานะเพื่อเป็นทางเลือกเพิ่มเติมให้ อย่างไรก็ตาม แนวคิดหลักในการทำสัญลักษณ์จะยังคงเหมือนกับที่กล่าวไว้ข้างต้นแทบทุกประการ
2. จะนำเสนอการค้นหาในแนวกว้าง(ซึ่งในความเป็นจริง ผู้ทำโจทย์สามารถเลือกใช้วิธีอื่นได้) ซึ่งใช้แถวคอย (queue) เก็บพิกัดของคนที่อยู่ติดกับคนปัจจุบัน ที่เลือกใช้แถวคอยช่วยในการค้นหาเพราะเนื่องจากเราจะค้นหาในแนวกว้าง เราจะไล่จากพิกัดปัจจุบัน แล้วค่อยไล่พิกัดที่อยู่รอบๆพิกัดปัจจุบันทั้งหมดต่อ แถวคอยจึงเป็นโครงสร้างข้อมูลที่รองรับการทำงานประเภทนี้ที่สุด

(อธิบายข้อ 2 ย่อยเพิ่มว่าทำไมใช้แถวคอย) เช่นเราได้พิกัดมาเป็น

$\begin{matrix} 1 & 1 & 1\\ 1 & 1 & 0 \end{matrix}$

แล้วเราเริ่มตรวจที่พิกัด (0,0) ก่อน เราจะพบว่า (1,0) (1,1) และ (0,1) เป็นพิกัดรอบๆที่เป็น "1" เราจะไล่พิกัดเหล่านี้ก่อนพิกัด (0,2) ดังนั้นถ้าใช้แถวคอยช่วย จะได้ภาพดังนี้

[(0,0)]

เมื่อเราทำ (0,0) เสร็จก็นำออกจากแถวคอยแล้วทำการใส่พิกัดรอบๆลงไป จะได้

[(1,0),(1,1),(0,1)]

และเมื่อทำทั้งสามพิกัดนี้เสร็จแล้วใส่พิกัดที่อยู่รอบๆที่เป็น "1"ไปอีกจะได้

[(0,2)]

เมื่อทำพิกัดในแถวคอยชุดนี้เสร็จก็ใส่พิกัดที่อยู่รอบๆที่เป็น "1"ไปอีกจะได้

[]

แถวคอยเปล่านั่นเอง ถือว่าจบการค้นหาในรอบนี้ ทำขีดลงกระดาษลงไป 1 ขีดเพื่อนับว่านับไปแล้วอีก 1 กลุ่ม

แล้วเราก็ทำการค้นหาด้วยแนวคิดเดียวกันนี้ไปเรื่อยๆจนกว่าจะครบทั้งตาราง

Solution Writer's Code in C++ Language

#include <bits/stdc++.h>
using namespace std;
char w[2005][2005]; //ใช้เก็บข้อมูลที่โจทย์ให้มา
int main() {
  int m, n;
  scanf("%d%d", &m, &n); //เก็บจำนวนแถวกับคอลั่มน์
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      scanf(" %c", &w[i][j]);
  queue<pair<int, int>> q; //ใช้เก็บพิกัดในการค้นหาตามแนวกว้าง
  int di[8][2] = {
      {1, 0}, {-1, 0}, {0, 1},  {0, -1},
      {1, 1}, {-1, 1}, {1, -1}, {-1, -1}}; //เอาไว้วนเช็คพิกัดรอบๆพิกัดปัจจุบันทั้ง 8 ทิศ
  int ans = 0;                             //ใช้นับว่ามีคนทั้งหมดที่กลุ่ม
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      if (w[i][j] == '1') {
        ans++;
        q.emplace(i, j);
        while (!q.empty()) {
          pair<int, int> f = q.front(); //ดึงข้อมูลตัวหน้าสุดของ queue
          q.pop();
          int x = f.first, y = f.second;
          if (w[x][y] == '0')
            continue;
          w[x][y] = '0';
          for (int k = 0; k < 8; k++) {
            int xx = x + di[k][0], yy = y + di[k][1]; //เก็บหนึ่งในพิกัดรอบๆพิกัดปัจจุบัน
            if (xx < 1 || xx > m || yy < 1 ||
                yy > n) //ตรวจสอบว่าไม่เกินตารางในความเป็นจริง
              continue;
            if (w[xx][yy] == '1')
              q.emplace(xx, yy);
          }
        }
      }
  printf("%d", ans);
}

Time Complexity : $\mathcal{O}{(\mid V\mid^2)}$