SPOJ PTIT135F - Đếm cửa sổ

Link đề bài

Hướng dẫn giải: Ở đây ta không cần duyệt hết từng phần tử của lưới mà chỉ cần duyệt các điểm tô đỏ dưới đây:

################
#****#****#****#
#****#****#****#
#****#....#****#
#....#....#****#
################
#....#****#****#
#....#****#....#
#....#....#....#
#....#....#....#
################

(Test mẫu số 2)

Xét ô cửa tiêu chuẩn (6x6):

######
#****# <- Dòng 1
#****# <- Dòng 2
#****# <- Dòng 3
#****# <- Dòng 4
###### (Ô này đang ở trạng thái kéo 4/4 - trạng thái kết quả thứ 5)

• Nếu ô đầu tiên của dòng 4 là dấu * thì ô cửa kéo 4/4 - trạng thái thứ 5
• Nếu ô đầu tiên của dòng 3 là dấu * mà ô đầu dòng 4 khác * thì ô cửa kéo 3/4 - trạng thái thứ 4
• Tương tự với trạng thái thứ 3, thứ 2.
• Đến khi xét ô đầu dòng 1 khác * thì ô cửa kéo 0/4 - trạng thái thứ 1

Kết hợp với phép đếm, ta dễ dàng tìm được kết quả theo đề bài.

Code mẫu (C)

Update: một bài tập khác cũng có nội dung tương tự là PTITSU1D. Lời giải cho bài tập này, xem tại đây.

Happy coding!