Đây là 1 bài khá lâu rồi ! Bài này thú thật là giải cũng không ra^^ nhưng thôi mình post lên cho các bạn tham khảo. Cá nhân mình thấy bài này thực sự cũng rất hay, dành cho những bạn đang làm quen với phương pháp quay lùi và thử sai. Cách giải mình nêu ra sau đây là của Hailoc.
Ý tưởng như sau :
Xét một ô, nếu 7 trong 8 ô xung quanh nó đều đã biết có mìn hay không thì có thể suy ra được ô còn lại có mìn hay không.
Giả sử đã biết được toàn bộ các ô hàng trên cùng và hàng ngoài cùng bên trái có mìn hay không ( dùng đệ quy quay lui để tạo ra giả thiết này )
Xét ô đặc biệt là ô ở góc trái trên (1, 1), xung quanh nó chỉ có 3 ô, như vậy nếu biết được 2 ô xung quanh: 1 ô nằm ở hàng trên cùng(1, 2), 1 ô nằm ở hàng ngoài cùng bên trái (2,1 )thì ta có thể suy ra được ô thứ ba (1, 1). Lúc này ô (2, 2) lại đóng vai trò như ô (1, 1) ban nãy do đó ta tìm được (3,2). Làm lần lượt ta tìm được toàn bộ bảng. Nếu có một bước nào đó không thực hiện được thì chứng tỏ giả thiết là sai, tiếp tục thực hiện đệ quy quay lui.
Để giảm tính toán ta không nhất thiết phải tính toàn bộ hàng trên cùng và hàng ngoài cùng rồi mới suy ra toàn bảng để kiểm tra mà có thể vừa tính vừa suy, cụ thể suy ra toàn bộ hàng ngoài cùng bên trái, sau đó mỗi lần chạy đệ quy với một ô của hàng trên cùng ta xác định tất cả các ô cùng cột với nó có mìn hay không. Nếu ở bước nào đó không xác định được thì quay lui.
nguyên văn bởi Hailoc
Bài này có 3 hàm cần chú ý :
hàm thứ nhất là :
Thử sai theo cột
void try_ver(int i)
{
if (i == row) try_hor(1);
else
{
/*Có thể đặt thêm điều kiện ở đây để hạn chế số lần thử sai*/
for ( int j = 1; j >= 0; j-- )
{
mine[i][0]=j;
try_ver(i+1);
}
}
}
Bản đồ sẽ có dạng :
1 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0
Tức là ta gán thử như trong ý tưởng, ví dụ ô mine[0][1] = 1 và tiếp tục là thử sai theo hàng .
void try_hor(int i)
{
if (i == col) print();
else
{
for ( int j = 0; j <= 1; j++ )
{
mine[0][i]= j;
if ( possible(i))
try_hor(i+1);
}
}
}
Tiếp theo ta thử hàng thứ i + 1 ( try_hor(i+1) )
Và lúc này ta vừa thử vừa kiểm tra bằng hàm :
int possible(int j) /*chú ý j ở đây là cột*/
{
int count;
for ( int i = 1; i < row; i++) //i la hang
{
count = 0;
mine[i][j]=0; /*Đây chính là ô ta cần suy diễn ra nên không tính vào, đó là lý do vì sao gán nó = 0*/
for (int k = 0; k < 8; k++) /*kiểm tra các ô xung quanh ô[i-1][j-1], chú ý là ta cần kiểm tra ô [i-1][j-1] để suy ra ô ta đanh xét, đây cũng chính là ý tưởng chính của bài này */
{
/*Kiểm tra xem các ô xung quanh có nằm trong bảng hay không, ta có thể thay bằng kĩ thuật lính canh ở đây thế câu lệnh if trong phần khởi tạo bảng*/
if( ((j-1+ver[k])>=0) && ((j-1+ver[k])< col) && ((i-1+hor[k])>=0) && ((i-1+hor[k]) < row))
{
count += mine[i-1+hor[k]][j-1+ver[k]];
}
}
/*Nếu số bom trong bảng trừ đi số bom đếm thử = 0 thì có nghĩa là ô đang xét là 0, và nếu = 1 thì tức là cần thêm 1 trái bom suy ra ô đó = 1.*/
switch ( board[i-1][j-1] - count )
{
case 0: mine[i][j]=0; break;
case 1: mine[i][j]=1; break;
default : return false; /* Nếu không phải 0 hay 1 thì tức là sai*/
}
}
}
Vậy là bài toán đã được giải quyết, sau đây là toàn bộ code bằng C++:
#include <stdio.h>
#include <fstream>
#include <iomanip>
#define FI "mine.inp"
#define MAXN 100
int row, col;
int board[MAXN][MAXN];
int mine[MAXN][MAXN];
int hor[8] = {-1,-1,+0,+1,+1,+1,+0,-1};
int ver[8] = {+0,-1,-1,-1,+0,+1,+1,+1};
void input()
{
ifstream F;
F.open(FI);
F >> row >> col;
F.ignore();
for ( int i = 0; i < row; i++){
for( int j = 0; j < col; j++){
F >> board[i][j];
}
F.ignore();
}
F.close();
}
void initialization()
{
for ( int i = 0; i < row; i++ ){
for ( int j = 0; j < col; j++){
mine[i][j] = 0;
}
}
}
void print()
{
for( int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
cout << mine
[i
][j
] << setw
(3); }
}
}
int possible(int j)//j la cot
{
int count;
for ( int i = 1; i < row; i++) //i la hang
{
count = 0;
mine[i][j]=0;
for (int k = 0; k < 8; k++)
{
if( ((j-1+ver[k])>=0) && ((j-1+ver[k])< col) && ((i-1+hor[k])>=0) && ((i-1+hor[k]) < row))
{
count += mine[i-1+hor[k]][j-1+ver[k]];
}
}
switch ( board[i-1][j-1] - count )
{
case 0: mine[i][j]=0; break;
case 1: mine[i][j]=1; break;
default : return false;
}
}
}
void try_hor(int i)
{
if (i == col) print();
else
{
for ( int j = 0; j <= 1; j++ )
{
mine[0][i]= j;
if ( possible(i))
try_hor(i+1);
}
}
}
void try_ver(int i)
{
if (i == row) try_hor(1);
else
{
for ( int j = 1; j >= 0; j-- )
{
mine[i][0]=j;
try_ver(i+1);
}
}
}
void main()
{
input();
initialization();
try_ver(0);
}
File mine.inp
PHP Code:
10 15
0 3 2 3 3 3 5 3 4 4 5 4 4 4 3
1 4 3 5 5 4 5 4 7 7 7 5 6 6 5
1 4 3 5 4 3 5 4 4 4 4 3 4 5 5
1 4 2 4 4 5 4 2 4 4 3 2 3 5 4
1 3 2 5 4 4 2 2 3 2 3 3 2 5 2
2 3 2 3 3 5 3 2 4 4 3 4 2 4 1
2 3 2 4 3 3 2 3 4 6 6 5 3 3 1
2 6 4 5 2 4 1 3 3 5 5 5 6 4 3
4 6 5 7 3 5 3 5 5 6 5 4 4 4 3
2 4 4 4 2 3 1 2 2 2 3 3 3 4 2
Còn đây là code của Hailoc viết bằng Pascal :
Code:
const fi='mine.inp';
fo='mine.out';
maxn= 100;
moveh: array[1..7] of integer=(-1,-1,0,1,1,0,-1);
movec: array[1..7] of integer=(0,-1,-1,-1,0,1,1);
var m,n : integer;
f:text;
board: array[0..maxn+1, 0..maxn+1] of byte;
mine: array[-1..maxn+2, -1..maxn+2] of byte;
procedure input;
var i, j: integer;
begin
assign(f, fi); reset(f);
readln(f, m ,n);
for i:=1 to m do
for j:=1 to n do read(f, board[i, j]);
close(f);
end;
procedure init;
begin
fillchar( board, sizeof(board), 4);
fillchar( mine, sizeof(mine), 0);
end;
{kiem tra xem co bom o o i, j khi dang xet toi hang h va cot c}
function kiemtra(i, j: integer): byte;
var k: integer;
count: integer;
begin
i:= i-1;
j:= j-1;
count:= 0;
for k:=1 to 7 do
if mine[i+moveh[k], j+ movec[k]]=1 then
begin
count:= count+1;
end;
if count= board[i, j]-1 then
kiemtra:= 0
else if count= board[i, j] then
kiemtra:= 1
else kiemtra:= 2;
end;
function suytiep(j: integer): boolean;
var i: integer;
begin
for i:= 2 to m do {duyet qua tung hang}
begin
case kiemtra(i, j) of
0: mine[i, j]:= 1;
1: mine[i, j]:= 0;
else
begin
suytiep:= false;
exit;
end;
end;
end;
suytiep:= true;
end;
procedure output;
var i, j, count: integer;
begin
assign(f, fo); rewrite(f);
count:= 0;
for i:=1 to m do
for j:=1 to n do count:= count + mine[i, j];
writeln(f, count);
for i:=1 to m do
begin
for j:=1 to n do write(f, mine[i, j], ' ');
writeln(f);
end;
close(f);
halt;
end;
procedure tryngang(i: integer);
var j: integer;
begin
if i> n then output
else
for j:= 0 to 1 do
begin
mine[1, i]:= j;
{inboard;
inmine;}
if suytiep(i) then {kiem tra xem ket qua co bi sai khong}
tryngang(i+1)
end;
end;
procedure trydoc(i: byte);
var j:byte;
begin
if i> m then
tryngang(2)
else
for j:=1 downto 0 do
if board[i-1, 1] >= mine[i-2,1]+j then
begin
mine[i,1]:= j;
trydoc(i+1);
end;
end;
procedure main;
begin
init;
input;
trydoc(1);
writeln('Khong tim duoc');
end;
begin
main;
end.
Power Member
Minesweeper - Dò mìn sử dụng kỹ thuật nhánh cận
Quyền hạn của bạn