Bài toán dò mìn qua bản đồ mật độ

Hau_Koi · June 28, 2019, 4:15pm

bạn nào có lời giải bài này không. Mình hì hục code mấy hôm mà không ra

Cho 1 bãi mìn kích thước mxn ô vuông, trên 1 ô có thể có chứa 1 quả mìn hoặc không, để biễu diễn bản đồ mìn đó người ta có 2 cách :

Cách 1: dùng bản đồ đánh dấu: sử dụng 1 lưới ô vuông kích thước mxn, trên đó tại ô (i,j) ghi số 1 nếu ô đó có mìn, ghi số 0 nếu ô đó không có mìn.

Cách 2: dùng bản đồ mật độ: sử dụng 1 lưới ô vuông kíck thước mxn, trên đó tại ô (j,j) ghi 1 số trong khoảng từ 0->8 cho biết tổng số mình trong các ô lân cận với ô (i,j) ( ô lân cận với ô (i,j) là ô có chung với ô (i,j) ít nhất 1 đỉnh ) Giả thiết rằng 2 bản đồ được ghi chính xác theo tình trạng mìn trên hiện trường. Về nguyên tắc, lúc cài bãi mìn phải vẽ cả bản đồ đánh dấu và bản đồ mật độ, tuy nhiên sau 1 thời gian dài, khi người ta muốn gỡ mìn ra khỏi bãi thì vấn đề hết sức khó khăn bởi bản đồ đánh dấu đã bị thất lạc !! Công việc của các lập trình viên là: Từ bản đồ mật độ, hãy tái hiện lại bản đồ đánh dấu của mìn.

Dữ liệu: vào từ file văn bản MINE.INP, các số trên 1 dòng cách nhau ít nhất 1 dấu cách : + dòng 1 : ghi 2 số nguyên dương m, n ( 2 <= m, n <= 30 ) + m dòng tiếp theo, dòng thứ i ghi n số trên hàng i của bản đồ mật độ theo đúng thứ tự từ trái qua phải.

Kết quả: Ghi ra file văn bản MINE.OUT, các số trên 1 dòng ghi cách nhau ít nhất 1 dấu cách:

dòng 1: ghi tổng số mìn trong bãi.
m dòng tiếp theo, dòng thứ i ghi n số hàng i của bản đồ đánh dấu theo đúng thứ tự từ trái qua phải

Ví dụ:
MINE.INP
4 5
1 1 3 2 2
2 3 5 3 3
1 3 3 2 2
1 3 1 2 2
MINE.OUT
8
0 1 1 1 0
0 0 1 0 1
0 0 1 0 1
1 0 1 0 0

hungaya · June 28, 2019, 4:36pm

Ví dụ có vẻ sai sai:

Trong ma trận MINE.OUT có 9 quả mìn, nhưng sao lại ghi là 8 quả?
Trong MINE.INP, số 2 ở hàng 4 cột 5 (góc dưới bên phải) nói là xung quanh ô (4,5) có 2 quả mìn, nhưng sao trong MINE.OUT chỉ có 1 quả mìn xung quanh?

thaipt · June 28, 2019, 4:41pm

Theo mô tả thì bài này thật ra là giải thuật của trò chơi Minesweeper trên Windows (có sẵn trên Windows trước Windows 8). Tuy nhiên dường như ví dụ về Mine.inp và Mine.out lại không ăn khớp với nhau. Điển hình như một số trường hợp sau:

Ô[1,2] (hàng 1, cột 2 - tôi dùng quy ước hàng trước cột sau theo như đề bài và chỉ mục bắt đầu từ 1 chứ không phải 0) trên bản đồ mật độ có giá trị 1 nhưng lại có 2 mìn ở các ô lân cận (ở [1,3] và [2,3]), không kể chính nó. Theo định nghĩa về ô lân cận từ đề bài thì các ô [1,3] và [2,3] hoàn toàn thỏa mãn. Như vậy thì theo đề bài, ô[1,2] phải có giá trị là 2 hoặc 3 (Nếu kể luôn chính nó) thay vì 1.
Tương tự như vậy, ô [1,4] có giá trị là 2, nhưng chung quanh nó lại có đến 3 vị trí ([1,3], [2,3] và [2,5])
Và cuối cùng, định nghĩa về ô lân cận cũng mơ hồ: lân cận có bao gồm chính ô đang xét không? Nếu không thì tại sao ô [4,1] lại có giá trị 1? Nhưng nếu có thì tại sao ô [1,3] lại có giá trị 3 - đúng ra phải là 4.

Vì ví dụ không nhất quán với đề bài, tôi không thể trả lời chính xác cho bạn.

kisuluoibieng · June 28, 2019, 5:02pm

bạn code hì hục mấy hôm mà code gì mới được?
thông thường những bài như thế này cái khó nằm ở chỗ thuật toán/giải thuật, thời gian gõ code chỉ là một phần nhỏ so với thời gian suy nghĩ mà thôi

tntxtnt · June 28, 2019, 7:01pm

http://diendan.congdongcviet.com/threads/t2842::minesweeper-do-min-su-dung-ky-thuat-nhanh-can.cpp

http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

NP-complete nên em cứ thử 0-1 từng ô là được độ phức tạp O(2^mn)