Diện tích các khu vực

Trong một buổi thực tập tại bệnh viện, FullHouse Dev được giao nhiệm vụ phân tích sơ đồ các khu vực cách ly. Họ cần tính toán diện tích của từng khu vực riêng biệt để có thể lên kế hoạch bố trí nhân lực một cách hiệu quả.

Bài toán

Cho một lưới 2D. Ký tự '#' đại diện cho vách ngăn và ký tự '.' đại diện cho không gian trống. Bạn cần tìm diện tích của các khu vực không liên thông với nhau. Các ô \((i+1, j)\), \((i, j+1)\), \((i-1, j)\), \((i, j-1)\) được coi là kề với ô \((i, j)\).

Bài toán có nhiều test case.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Với mỗi test case:
  • Dòng đầu chứa hai số nguyên \(N\) và \(M\) - kích thước của lưới.
  • \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) ký tự ('#' hoặc '.').

OUTPUT FORMAT:

• Với mỗi test case:
  • Dòng đầu in ra số nguyên \(K\) - số lượng khu vực không liên thông.
  • Dòng thứ hai in ra \(K\) số nguyên - diện tích của từng khu vực theo thứ tự tăng dần.

Ràng buộc:

• Giới hạn thời gian: 2 giây
• Giới hạn bộ nhớ: 256MB

Ví dụ

INPUT

3
3 3
##.
..#
#.#
3 5
#.#.#
.#.#.
#.#.#
4 4
..##
..##
##..
##..

OUTPUT

2
1 3
7
1 1 1 1 1 1 1
2
4 4

Giải thích

Trong test case đầu tiên, có 2 khu vực không liên thông với diện tích lần lượt là 1 và 3 ô.