Chú ý: Bài này rất giống bài đếm số chòm sao và in ra số sao lớn nhất trong 1 chòm (Đề thi SVMC 6/2016)
Từ bức ảnh chụp từ đỉnh của một khách sạn hãy tính số người trung bình trên cả tầng đó.
'#' là tường
'-' là vị trí trống
'*' là vị trí bị chiếm bởi một người.
Ràng buộc.
dòng thứ nhất chứa số lượng test case
M N là kích thước ma trận, các dòng tiếp theo mô tả thông tin ma trận
Đầu ra:
Số người trung bình trong các phòng, độ chính xác 2 chữ số sau dấu phẩy.
Từ bức ảnh chụp từ đỉnh của một khách sạn hãy tính số người trung bình trên cả tầng đó.
'#' là tường
'-' là vị trí trống
'*' là vị trí bị chiếm bởi một người.
Ràng buộc.
- Ma trận đầu vào kích thước MxN với M,N<=100
- Số lượng test case nhỏ hơn 10
- Tất cả cạnh phía ngoài sẽ là tường
- Tối thiểu bài toán sẽ có 1 phòng
dòng thứ nhất chứa số lượng test case
M N là kích thước ma trận, các dòng tiếp theo mô tả thông tin ma trận
Đầu ra:
Số người trung bình trong các phòng, độ chính xác 2 chữ số sau dấu phẩy.
Ví dụ
Hướng dẫn giải:
Tại 1 điểm khác tường ta dùng DFS để gọi đệ quy duyệt tất cả các điểm lân cận và đánh dấu nó lại. Sau khi duyệt hết 1 phòng tìm điểm không phải là tường và chưa được đánh dấu để tiếp tục xét.
Tại 1 điểm khác tường ta dùng DFS để gọi đệ quy duyệt tất cả các điểm lân cận và đánh dấu nó lại. Sau khi duyệt hết 1 phòng tìm điểm không phải là tường và chưa được đánh dấu để tiếp tục xét.