Bài 37.13. Bản Đồ Số Hóa: Khai Thác Tài Nguyên - [Độ khó: Siêu khó]

Một công ty khai thác tài nguyên có một bản đồ khu vực dưới dạng ma trận. Mỗi ô trên bản đồ có thể là một loại tài nguyên quý hiếm (đánh dấu bằng số '1') hoặc đất trống (số '0'). Các khu vực tài nguyên quý hiếm được định nghĩa là các nhóm ô '1' liên thông theo chiều ngang hoặc dọc. Công ty muốn xác định từng khu vực tài nguyên riêng biệt và tính chu vi của mỗi khu vực. Chu vi được tính bằng tổng số cạnh của các ô '1' tiếp xúc với ô '0' hoặc biên của bản đồ.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên R và C (1 <= R, C <= 50), lần lượt là số hàng và số cột của bản đồ. R dòng tiếp theo, mỗi dòng chứa C số nguyên (0 hoặc 1), biểu diễn bản đồ.

OUTPUT FORMAT

In ra một dòng duy nhất: Tong chu vi cac khu vuc: X (trong đó X là tổng chu vi của tất cả các khu vực tài nguyên được tìm thấy trên bản đồ).

Ví dụ:

Input:

4 4
0 1 1 0
1 1 0 0
0 0 0 1
0 0 1 1

Output:

Tong chu vi cac khu vuc: 22

Giải thích: Có hai khu vực tài nguyên (các nhóm '1' liên thông): Khu vực 1:

. 1 1 .
1 1 . .
. . . .
. . . .

• Ô (0,1): 3 cạnh tiếp xúc '0' (trên, trái, phải). Cạnh dưới tiếp xúc (1,1). Chu vi = 3.
• Ô (0,2): 3 cạnh tiếp xúc '0' (trên, phải, trái). Cạnh dưới tiếp xúc (0,1). Chu vi = 3.
• Ô (1,0): 3 cạnh tiếp xúc '0' (dưới, trái, trên). Cạnh phải tiếp xúc (1,1). Chu vi = 3.
• Ô (1,1): 1 cạnh tiếp xúc '0' (dưới). Cạnh trên tiếp xúc (0,1), cạnh trái tiếp xúc (1,0). Chu vi = 1. Tổng chu vi khu vực 1 = 3 + 3 + 3 + 1 = 10.

Khu vực 2:

. . . .
. . . .
. . . 1
. . 1 1

• Ô (2,3): 3 cạnh tiếp xúc '0' (trên, phải, trái). Cạnh dưới tiếp xúc (3,3). Chu vi = 3.
• Ô (3,2): 3 cạnh tiếp xúc '0' (dưới, trái, trên). Cạnh phải tiếp xúc (3,3). Chu vi = 3.
• Ô (3,3): 2 cạnh tiếp xúc '0' (dưới, phải). Cạnh trên tiếp xúc (2,3), cạnh trái tiếp xúc (3,2). Chu vi = 2. Tổng chu vi khu vực 2 = 3 + 3 + 2 = 8.

Tổng chu vi tất cả khu vực = 10 + 8 = 18.

Lỗi trong giải thích ví dụ: (0,2) bên phải không phải 0 mà là biên. (1,1) dưới nó là (2,1) là 0. Hãy tính lại theo quy tắc: Chu vi là tổng số cạnh của các ô '1' tiếp xúc với ô '0' HOẶC biên của bản đồ. Bản đồ:

0 1 1 0  (0,0) (0,1) (0,2) (0,3)
1 1 0 0  (1,0) (1,1) (1,2) (1,3)
0 0 0 1  (2,0) (2,1) (2,2) (2,3)
0 0 1 1  (3,0) (3,1) (3,2) (3,3)

Khu vực 1: (0,1), (0,2), (1,0), (1,1)

• (0,1): (trên biên) + (trái 0,0) + (dưới 1,1) + (phải 0,2) -> 1 (biên) + 1 (0) + 0 (1) + 0 (1) = 2
  • Cạnh trên tiếp xúc biên: +1
  • Cạnh trái tiếp xúc (0,0)='0': +1
  • Cạnh phải tiếp xúc (0,2)='1': +0
  • Cạnh dưới tiếp xúc (1,1)='1': +0 -> Chu vi riêng = 2
• (0,2): (trên biên) + (trái 0,1) + (dưới 1,2='0') + (phải biên) -> 1+0+1+1 = 3 -> Chu vi riêng = 3
• (1,0): (trên 0,0='0') + (trái biên) + (dưới 2,0='0') + (phải 1,1) -> 1+1+1+0 = 3 -> Chu vi riêng = 3
• (1,1): (trên 0,1) + (trái 1,0) + (dưới 2,1='0') + (phải 1,2='0') -> 0+0+1+1 = 2 -> Chu vi riêng = 2 Tổng khu vực 1 = 2 + 3 + 3 + 2 = 10. (Đã đúng với tính toán lúc trước)

Khu vực 2: (2,3), (3,2), (3,3)

• (2,3): (trên biên) + (trái 2,2='0') + (dưới 3,3) + (phải biên) -> 1+1+0+1 = 3 -> Chu vi riêng = 3
• (3,2): (trên 2,2='0') + (trái 3,1='0') + (dưới biên) + (phải 3,3) -> 1+1+1+0 = 3 -> Chu vi riêng = 3
• (3,3): (trên 2,3) + (trái 3,2) + (dưới biên) + (phải biên) -> 0+0+1+1 = 2 -> Chu vi riêng = 2 Tổng khu vực 2 = 3 + 3 + 2 = 8. (Đã đúng với tính toán lúc trước)

Tổng chu vi tất cả khu vực = 10 + 8 = 18. Vậy ví dụ output 22 là sai. Phải sửa thành 18.

Sửa lại Output ví dụ:

Output:
Tong chu vi cac khu vuc: 18