3. 유기농 배추

/** DFS랑 BFS 둘 다 가능~ */
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const N = parseInt(input.shift());

const ansewr = [];

for (let i = 0; i < N; i++) {
  const [M, N, K] = input[0].split(" ").map(Number);

  const board = [...new Array(M)].map(() => new Array(N).fill(0));

  for (let j = 0; j < K; j++) {
    const [a, b] = input[j + 1].split(" ").map(Number);
    board[a][b] = 1;
  }

  ansewr.push(solution(board, M, N));

  // input K+1 개 날려버리기
  input = input.slice(K + 1);
}

console.log(ansewr.join("\n"));

function solution(board, M, N) {
  let count = 0;

  // board 다 돌기
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (board[i][j]) {
        board[i][j] = 0;
        bfs(board, i, j, M, N);
        count++;
      }
    }
  }

  return count;
}

function bfs(board, i, j, M, N) {
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];

  const queue = [[i, j]];

  while (queue.length) {
    const [a, b] = queue.shift();

    for (let k = 0; k < 4; k++) {
      const nx = a + dx[k];
      const ny = b + dy[k];

      if (nx >= 0 && nx < M && ny >= 0 && ny < N && board[nx][ny]) {
        queue.push([nx, ny]);
        board[nx][ny] = 0; // 처음에 방문 처리를 큐에 넣기 전에 했음 (그랬더니 시간초과남)
      }
    }
  }
}