[jambon]

Bài này thì chắc chắn có nhiều người làm rồi nhưng tui vẫn muốn đưa ra để mọi người góp ý cho vui. Vì làm rồi nên chắc chắn các bạn còn nhớ lời giải.

Mine Sweeper.

Nghe đầu đề là biết sao rồi. Nhưng đã mất công viết thì xin nêu qua lại đề bài cho các bạn chưa bao giờ làm.

Ma trận A[m * n], giá trị A[i,j] = 1 nếu ô (i,j) có mìn, A[i,j] = 0 nếu ô (i,j) không có mìn.
Ma trận B[m * n] được tạo như sau: B[u,v] = tổng các ô có mìn xung quanh ô (u,v). Nhiều nhất là 8 ô, kề cạnh, kề đỉnh.

Nếu yêu cầu cho mảng A rồi suy ra B thì chắc cả forum chửi tui mất. Bây giờ cho B suy ra A thì chắc một nửa chửi tui ra bài dễ quá.

Nhưng yêu cầu là cho B và suy ra A.

Chúng ta hãy bàn luận về thuật toán đi nào. Have fun everyone.

[jambon]

Xin mở đầu, lần đầu tiên tui làm bài này, giới hạn M, N chỉ có là 20 thôi. Nhưng với trình độ lúc đó, làm cả tuần chả xong được. Đã thế chạy thì chậm hơn con rùa nữa.

Các chú thì sao? Chương trình của các chú chạy được với M, N đến bao nhiêu ? Thời gian tìm nghiệm nữa ?

[jambon]

Anh "Phù Thủy" là anh nào thế? Cách làm của chú như thế nào? Gợi ý cho mọi người, thời gian quái đâu mà đọc code của chú.

[jambon]

Lão Tuấn nào thế? Chương trình của tui cũng chạy được cỡ 170 x 170.
Tui cũng duyệt từ góc (1,1). Tất nhiên cũng là duyệt nhưng không đặt 0, với 1. Tui dựa vào giá trị để suy ra các trạng thái xung quanh.
Chẳng hạn như ô (1,1) có giá trị 3 thì chú cần gì phải thử đặt giá trị 0 cho các ô xung quanh nó. Nếu kiểm soát tốt thì có lẽ nhanh hơn chương trình của chú.