Bài Toán Dò Mìn

[tungbvit]

Các bạn giỏi pascal giải dùm mính pài này nha :
Cho một bãi mìn kích thước mxn
Bãi mìn được xác định bởi hai loại bản đồ :
- Bản đồ vị trí với quy ước : 0 nếu tại đó không có mìn; 1 nếu ngược lại.
-Bản đồ mật độ với quy ước : điểm A[i,j] (A: bãi mìn; 1<=i<=m; 1<=j<=n) chứa giá trị là tổng số mìn chung quanh nó (trừ nó ra).
Yêu cấu : nhập m,n và bản đồ mật độ. Lập trình để từ bản đồ mật độ suy ra được bản đồ vị trí.
Vd:
Input :
1 3 3 3 3 1
2 5 4 4 4 2
4 5 4 3 3 1
2 3 3 1 2 1
Out:
1 0 0 1 1 0
1 0 1 1 0 0
0 1 1 0 0 1
1 1 0 0 0 1

[nguyenle]

Các bạn giỏi pascal giải dùm mính pài này nha :
Cho một bãi mìn kích thước mxn
Bãi mìn được xác định bởi hai loại bản đồ :
- Bản đồ vị trí với quy ước : 0 nếu tại đó không có mìn; 1 nếu ngược lại.
-Bản đồ mật độ với quy ước : điểm A[i,j] (A: bãi mìn; 1<=i<=m; 1<=j<=n) chứa giá trị là tổng số mìn chung quanh nó (trừ nó ra).
Yêu cấu : nhập m,n và bản đồ mật độ. Lập trình để từ bản đồ mật độ suy ra được bản đồ vị trí.
Vd:
Input :
1 3 3 3 3 1
2 5 4 4 4 2
4 5 4 3 3 1
2 3 3 1 2 1
Out:
1 0 0 1 1 0
1 0 1 1 0 0
0 1 1 0 0 1
1 1 0 0 0 1

Nói rõ đề chút được không bạn, mình không hiểu đề lắm.
1. Bản đồ của bạn có dạng 1 ma trận ( Mảng 2 chiều). Hay dạng nào?

-Bản đồ mật độ với quy ước : điểm A[i,j] (A: bãi mìn; 1<=i<=m; 1<=j<=n) chứa giá trị là tổng số mìn chung quanh nó (trừ nó ra).

2.Chung Quanh là ở đâu, tấc cả các ô còn lại hay các ô nào?
3.Các con số cho ở Input có ý nghĩa gì?...

[vanvuive]

Bài toán đưa ra không rõ ràng về input và ý nghĩa lắm, Đề nghị bạn cung cấp thêm thông tin#-o

[vemaybayvietmy06]

các bạn chơi trò dò mìn trong máy k ? Đọc kĩ lại đề xem [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG] . Chung wanh là 9 ô

[muabuon]

Bài toán trên phát triển thành bài “Hình chữ nhật có chôn mìn”.
Cho một sân hình chữ nhật kích thước MxN ô vuông. Trên mỗi ô vuông có thể chôn hoặc không chôn 1 quả mìn. Tình trạng bãi mìn có thể được mô tả bở một trong 2 cách sau:
+ Cách 1: Dùng một mảng MIN1[1..M, 1..N] trong đó MIN1[i, j] =0/1 tùy thuộc ô (i, j) không có hoặc có mìn.
+ Cách 2: Mỗi ô của sân có nhiều nhất 8 ô kề với nó (hình 1). Ta cho tương ứng các ô này với các số 1, 2, 4, 8, 16, 32, 64, 128 như hình 1. Khi đó ta lập mảng MIN2[1..M, 1...N] như sau: MIN2[i, j] bằng tổng các số hạng có dạng X.Y trong đó X là số tương ứng với một ô kề với nó, Y bằng 1/0 tùy theo ô đó có mìn hay không, ô (i, j) có bao nhiêu ô kề thì có bấy nhiêu số hạng. Trong hình 2 cho ví dụ về cách lập bảng MIN2 ứng với tình trạng mìn cho bởi mảng MIN1.

1     2     4             1   0   1          16   184   96
128  ô i,j   8            0   1   1          58    109   194
64   32     16            1   1   0          12   134    131
                                MIN1                  MIN2
    Hình 1                             Hình 2:

Viết chương trình thực hiện các việc sau:
1.Đọc từ file MIN1.INP có cấu trúc: dòng đầu ghi 3 số M, N, S (S <=100). Trong M dòng sau, dòng thứ i+1 ghi lần lượt N số MIN1[i,1], …, MIN1[i,N]. Sau đó ghi vào file MIN1.OUT mảng MIN2 thể hiện theo cách 2 tình trạng bãi mìn cho bởi mảng MIN1.
2.Đọc từ file MIN2.INP có cấu trúc giống MIN1.INP nhưng các số là của mảng MIN2[i, j]. Sau đó ghi ra file MIN2.OUT tình trạng bãi mìn theo cách thứ nhất.

[ducquan1008]

2 bài này # nhau hoàn toàn mà a

[thienho]

Ừa! Đúng rồi. Nãy không đọc kỹ nên nhầm mất. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
Có ai có ý kiến nào về ý tưởng không?

[dakasakoru]

Các bạn đóng góp ý kiến nhé!

Uses Crt;
Const
        c = 100;
Type
        ma = Array[0..c+1, 0..c+1] Of Byte;
Var
        f : Text;
        m, n : Byte;
        min1, min2 : ma;

Procedure doc(st : String; Var x : ma);
Var i, j : Byte;
Begin
        Assign(f, st);
        Reset(f);
        Readln(f, m, n);
        For i := 1 To m Do
        Begin
                For j := 1 To n Do Read(f, x[i, j]);
                Readln(f);
        End;
        Close(f);
End;

Procedure ghi(st : String; x : ma);
Var i, j : Byte;
Begin
        Assign(f, st);
        Rewrite(f);
        For i := 1 To m Do
        Begin
                For j := 1 To n Do Write(f, x[i, j], ' ');
                Writeln(f);
        End;
        Close(f);
End;

Procedure doi12;
Var i, j, s : Byte;
Begin
        For i := 1 To m Do
        Begin
                min1[i, 0] := 0;
                min1[i, n+1] := 0;
        End;
        For i := 1 To m Do
        For j := 1 To n Do
        Begin
                s := min1[i-1, j-1] + min1[i-1, j]*2 + min1[i-1, j+1]*4;
                s := s + min1[i, j+1]*8 + min1[i+1, j+1]*16 + min1[i+1, j]*32;
                s := s + min1[i+1, j-1]*64 + min1[i, j-1]*128;
                min2[i, j] := s;
        End;
End;

Procedure doi21;
Var i, j, k : Byte;
Begin
        For i := 1 To m Do
        For j := 1 To n Do
        If min2[i, j] = 0 Then
        Begin
                min1[i-1, j+1] := 0; min1[i-1, j] := 0;
                min1[i-1, j-1] := 0; min1[i, j-1] := 0;
                min1[i+1, j-1] := 0; min1[i+1, j] := 0;
                min1[i+1, j+1] := 0; min1[i, j+1] := 0;
        End
        Else
        Begin
                k := min2[i, j];
                If k >= 128 Then
                Begin
                        min1[i, j-1] := 1;
                        k := k - 128;
                End
                Else min1[i, j-1] := 0;
                If k >= 64 Then
                Begin
                        min1[i+1, j-1] := 1;
                        k := k - 64;
                End
                Else min1[i+1, j-1] := 0;
                If k >= 32 Then
                Begin
                        min1[i+1, j] := 1;
                        k := k - 32;
                End
                Else min1[i+1, j] := 0;
                If k >= 16 Then
                Begin
                        min1[i+1, j+1] := 1;
                        k := k - 16;
                End
                Else min1[i+1, j+1] := 0;
                If k >= 8 Then
                Begin
                        min1[i, j+1] := 1;
                        k := k - 8;
                End
                Else min1[i, j+1] := 0;
                If k >= 4 Then
                Begin
                        min1[i-1, j+1] := 1;
                        k := k - 4;
                End
                Else min1[i-1, j+1] := 0;
                If k >= 2 Then
                Begin
                        min1[i-1, j] := 1;
                        k := k - 2;
                End
                Else min1[i-1, j] := 0;
                If k >= 1 Then
                Begin
                        min1[i-1, j-1] := 1;
                        k := k - 1;
                End;
        End;
End;

Begin
        doc('min1.inp', min1);
        doi12;
        ghi('min1.out', min2);
        doc('min2.inp', min2);
        doc21;
        ghi('min2.out', min1);
End.

[dichvutonghop]

e chỉ bik way lui trên mảng 2 chiều thôi . Code mãi , chưa ra [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG](

[damynghebaoan]

Gợi ý nè!!

Các bạn giỏi pascal giải dùm mính pài này nha :
Cho một bãi mìn kích thước mxn
Bãi mìn được xác định bởi hai loại bản đồ :
- Bản đồ vị trí với quy ước : 0 nếu tại đó không có mìn; 1 nếu ngược lại.
-Bản đồ mật độ với quy ước : điểm A[i,j] (A: bãi mìn; 1<=i<=m; 1<=j<=n) chứa giá trị là tổng số mìn chung quanh nó (trừ nó ra).
Yêu cấu : nhập m,n và bản đồ mật độ. Lập trình để từ bản đồ mật độ suy ra được bản đồ vị trí.
Vd:
Input :
1 3 3 3 3 1
2 5 4 4 4 2
4 5 4 3 3 1
2 3 3 1 2 1
Out:
1 0 0 1 1 0
1 0 1 1 0 0
0 1 1 0 0 1
1 1 0 0 0 1

Đặt cái mảng Input là Min1 zới Output là Min2 nha.
Mình gợi ý cho bạn nè.
_ Bạn sử dụng quay lui trên mảng 2 chiều.
_ i>m thì print và exit;
_ Else thì cho Min2[i,j] nhận gtrị là 0 hoặc 1.
_ Nếu x[i,j]=1 thì giảm (Min1[i-1,j-1]..Min1[i+1,j+1]) 1 đvị, nhớ cộng lại 1 cho Min1[i,j] nha.
_ Đkiện để xét tiếp là :
+ Nếu (i=m) và (1<j<n) và Min1(i,j-1)=0;
+ Nếu (j=n) và (1<i<m) và Min1(i-1,j)=0;
+ Nếu (1<i<m) và (1<j<n) và Min1(i-1,j-1)=0;
--> Đúng thì nếu j<n thì Xet(i,j+1) else Xet(i+1,1);
-->Ko đúng thì quay lui và tăng lại mấy ô xung quanh.

Chúc bạn thành công.