Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: Minesweeper - Dò mìn sử dụng kỹ thuật nhánh cận

  1. #1
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định Minesweeper - Dò mìn sử dụng kỹ thuật nhánh cận

    Code:
    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 4
    
    1 1 3 2 2
    2 3 5 3 3
    1 3 3 2 2
    1 3 1 2 2
    
    MINE.INP
    8
              
    0 1 1 1 0
    0 0 0 1 0
    1 0 0 1 0
    1 0 1 0 0
    Bài này trong chương nhánh cận của cuốn DASP của tác giả Lê Minh Hoàn, ai có ý tưởng gì thì xin giúp mình ! Mình thực sự không biết đánh giá nhánh cận ra sao, hic hic vì nếu quay lùi đơn thuần thì phải 2^mxn, hic hic! Cám ơn các bạn trước nhé !
    Đã được chỉnh sửa lần cuối bởi rox_rook : 08-07-2007 lúc 10:25 AM.

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Em thấy có thể áp dụng nhánh cận này: Điều kiện để một ô có thể có mìn là 8 ô xung quanh nó không ô nào có mật độ bằng 0. Sau khi đánh dấu ô đó có mìn ta giảm giá trị của 8 ô xung quanh lênh 1, khi quay lui thì tăng 8 ô lên 1.

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Bài này hay đấy , nhưng giờ phải vào kiểm tra rồi . Tối về suy nghĩ thử xem sao ?
    Cách của HL ko khả thi lắm .Ví dụ như ở bản đồ trên thì cách của HL ko áp dụng được rồi . Có phải ko nhỉ ?

  4. #4
    Ngày gia nhập
    04 2007
    Bài viết
    16

    Bài này trong chương nhánh cận của cuốn DASP của tác giả Hoàng kiếm, ai có ý tưởng gì thì xin giúp mình ! Mình thực sự không biết đánh giá nhánh cận ra sao, hic hic vì nếu quay lùi đơn thuần thì phải 2^mxn, hic hic! Cám ơn các bạn trước nhé !
    Đây là bài trong cuốn DSAPTextbook của thầy Lê Minh Hoàng!!!
    Bài này quay lui, độ phức tạp là 2^(m+n) thôi, với nhận xét: Nếu biết được rõ 3: trái, trên và trái trên của một ô thì có thể xác định ngay xem ô đó có mìn hay không.
    Quay lui, chỉ duyệt hàng 1 và cột 1 thôi.

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    ặc ! Sorry ! Nhầm tên tác giả , hic hic ! Cám ơn hd_kinh_can đã nhắc nhở T_T

  6. #6
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Mặc định Minesweeper - Dò mìn sử dụng kỹ thuật nhánh cận

    Hay nhỉ ! Để load cuốn này về xem source ra sao ? Ko nghĩ được gì . Bài này hay quá .

  7. #7
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Đâ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++:
    C++ Code:
    1.  
    2. #include <stdio.h>
    3. #include <fstream>
    4. #include <iomanip>
    5.  
    6. #define FI "mine.inp"
    7. #define MAXN 100
    8.  
    9. int row, col;
    10. int board[MAXN][MAXN];
    11. int mine[MAXN][MAXN];
    12. int hor[8] = {-1,-1,+0,+1,+1,+1,+0,-1};
    13. int ver[8] = {+0,-1,-1,-1,+0,+1,+1,+1};
    14.  
    15. void input()
    16. {
    17.         ifstream F;
    18.         F.open(FI);
    19.         F >> row >> col;
    20.         F.ignore();
    21.        
    22.         for ( int i = 0; i < row; i++){
    23.                 for( int j = 0; j < col; j++){
    24.                         F >> board[i][j];
    25.                 }
    26.             F.ignore();
    27.         }
    28.         F.close();
    29. }
    30. void initialization()
    31.  
    32.     {        
    33.         for ( int i = 0; i < row; i++ ){
    34.                 for ( int j = 0; j < col; j++){
    35.                         mine[i][j] = 0;
    36.                 }
    37.         }
    38. }
    39.  
    40. void print()
    41.    
    42.     {
    43.         for( int i = 0; i < row; i++){
    44.                 for (int j = 0; j < col; j++){
    45.                         cout << mine[i][j] << setw(3);
    46.                 }
    47.                 cout << "\n\n";
    48.         }
    49. }
    50.  
    51. int possible(int j)//j la cot
    52.  
    53.     {
    54.     int count;
    55.     for ( int i = 1; i < row; i++) //i la hang
    56.     {
    57.         count = 0;
    58.         mine[i][j]=0;
    59.         for (int k = 0; k < 8; k++)
    60.                 {
    61.            
    62.             if( ((j-1+ver[k])>=0) && ((j-1+ver[k])< col) && ((i-1+hor[k])>=0) && ((i-1+hor[k]) < row))
    63.             {
    64.                                 count += mine[i-1+hor[k]][j-1+ver[k]];
    65.             }
    66.         }
    67.         switch ( board[i-1][j-1] - count )
    68.         {
    69.             case 0: mine[i][j]=0; break;
    70.             case 1: mine[i][j]=1; break;
    71.             default : return false;
    72.         }
    73.              
    74.     }
    75. }
    76.  
    77. void try_hor(int i)
    78.  
    79.     {
    80.     if (i == col) print();
    81.     else
    82.     {
    83.         for ( int j = 0; j <= 1; j++ )
    84.         {
    85.             mine[0][i]= j;
    86.             if ( possible(i))
    87.                                 try_hor(i+1);
    88.         }
    89.         }
    90. }
    91.  
    92. void try_ver(int i)
    93.  
    94.     {
    95.         if (i == row) try_hor(1);
    96.         else
    97.         {
    98.         for ( int j = 1; j >= 0; j-- )
    99.         {
    100.             mine[i][0]=j;
    101.             try_ver(i+1);
    102.         }
    103.         }
    104. }
    105.  
    106. void main()
    107. {
    108.     input();
    109.         initialization();
    110.         try_ver(0);
    111.        
    112.         cin.get();
    113. }
    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.
    Đã được chỉnh sửa lần cuối bởi rox_rook : 02-03-2008 lúc 02:53 AM.

  8. #8
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Bài Minesweeper này đúng là một bài rất thú vị nếu bạn nào đã quen với thao tác duyệt thông thường thì rất nên thử qua bài này.

  9. #9
    Ngày gia nhập
    10 2007
    Bài viết
    12

    Bài toán này có không gian tìm kiếm cỡ 2^(m*n). Vì vậy điều quan trọng nhất là phải tìm cách cắt bớt các nhánh của cây tìm kiếm.
    Có một cách đơn giản đó là lập một mảng neighbour[n][m] để đếm số lượng ô lân cận có mine trong quá trình thử. Khi neighbour[i][j] nào đó = board[i][j] thì lập tức ta gán các ô lân cận với mine[i][j] chưa được xét với 0 do đó ta có thể giảm đáng kể kích thước cây tìm kiếm.

  10. #10
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bài toán này có không gian tìm kiếm cỡ 2^(m*n). Vì vậy điều quan trọng nhất là phải tìm cách cắt bớt các nhánh của cây tìm kiếm.
    Có một cách đơn giản đó là lập một mảng neighbour[n][m] để đếm số lượng ô lân cận có mine trong quá trình thử. Khi neighbour[i][j] nào đó = board[i][j] thì lập tức ta gán các ô lân cận với mine[i][j] chưa được xét với 0 do đó ta có thể giảm đáng kể kích thước cây tìm kiếm.
    cám ơn bạn nhiều, ý tưởng này rất hay và cũng là điều mình thắc mắc lâu này tại sao nó nằm trong chương nhánh cận mà bài toán vẫn chưa vận dụng được điểm này, mình sẽ thử xem sao ! Thân !

Các đề tài tương tự

  1. Hướng dẫn viết game Dò mìn (Minesweeper) bằng C# + sourcecode
    Gửi bởi Yin Yang trong diễn đàn Tutorials và Thủ thuật lập trình C#, ASP.NET
    Trả lời: 23
    Bài viết cuối: 04-03-2013, 09:55 PM
  2. Dịch thuật, công ty dịch thuật, dịch vụ dịch thuật chuyên nghiệp
    Gửi bởi vecvn trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 4
    Bài viết cuối: 18-11-2012, 10:44 PM
  3. Dịch vụ kế toán: Báo cáo thuế, dịch vụ tư vấn thuế, báo cáo thuế tncn vnnp
    Gửi bởi ecomvnnp01 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 16-02-2012, 11:07 AM
  4. Source Game Minesweeper C++ (2 bài)
    Gửi bởi hoangnh1988 trong diễn đàn Dự án & Source code VC++
    Trả lời: 2
    Bài viết cuối: 23-03-2010, 10:03 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn