bài toán lưới mảng hai chiều

[tuan_anhhhh]

Cho lưới ô vuông kích thước M x N. các ô của lưới được sơn bởi một trong hai màu đen hăng trắng
Cần tìm hình vuông gồm toàn ô đen có kích thước lớn nhất
Dữ liệu vào:
File văn bản: LUOI.INP có cấu trúc như sau:
Dòng đầu ghi hai số M,N
Trong m dòng tiếp theo mỗi dòng ghi N số , trong đó a[I,j]=1 nếu ô (i.j) có màu đen và a[I,j]=0 nếu ô(I,j) có màu trắng
Kết quả:
Ghi ra file văn bản LUOI.OUT có cấu trúc như sau:
Dòng thứ nhất ghi số k là kích thước của hình vuông tìm được
Dòng thứ hai ghi 4 số p,q,r,s. trong đó (p,q) là tọa độ của ô ở góc trên trái còn (r,s) là tọa độ của ô ở góc dưới bên phải của hình vuông tim được.
Ví dụ:
LUOI.INP
8 10

0 1 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 1 1 1 1
0 0 1 1 1 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1

LUOI.OUT
4
5 6 8 9


có huynh vip nào có ý tưởng giải hay nói cho đệ nghe với

[NT_OnlyLove]

Cho lưới ô vuông kích thước M x N. các ô của lưới được sơn bởi một trong hai màu đen hăng trắng
Cần tìm hình vuông gồm toàn ô đen có kích thước lớn nhất

Mình có chút suy nghĩ thế này:

1.Khởi tạo các biến

  a. int count=0;//dùng lưu tình trạng diện tích hình vuông là lớn nhất
  b. int p,q,r,s để lưu tọa độ của bạn( thực ra cái này thừa) vì chỉ cần lưu p,  q (+ count) -> r,s.

1.Bạn cho chạy từ A[0][0] đến A[m][n]
2.Nếu gặp A[i][j]=1 thì bắt đầu kiểm tra loang bằng cách. Mở rộng diện tích từ count.
Duyệt hình vuông rộng ra bằng cách duyệt hình vuông cạch =count+1.
Nếu gặp 0 và cạnh < count+1 thì chuyển sang ô kề.
Ngược lại thì duyệt theo hình vuông xoắn ốc (hoặc kiểm tra các ô lân cận trong giới hạn hình vuông A[i+Count+1][j+Count+1]).
Nếu có ô bằng 0 thì chuyển ngược lại update các thông số Count, p, q, r, s.
3.Lặp lại như vậy cho đến hết

Đó là chút ý tưởng của mình. Để mình suy nghĩ thêm đã.

[Forlorn_hope]

Mình có ý nghĩ sau:
Với ma trận đã có như trên:
0 1 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 1 1 1 1
0 0 1 1 1 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
m=8, n=10
Ta làm như sau:

1. Lần lượt xét từng ô có giá trị là 1 trong ma trận 7*9. (Bởi hàng cuối và cột cuối chỉ bổ sung cho các ô vuông khi ta xét những ô ở hàng 7, và cột 9). Ma trận cần xét là màu đỏ.

0 1 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 1 1 1 1
0 0 1 1 1 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
2. Với 1 ô xét (màu đỏ) ta sẽ:
- int temp=1;
- Xét các ô kề (ô có màu xanh dương). Nếu các ô màu xanh dương đều là 1 ta sẽ xét tiếp các ô kề (ô màu xanh lá cây) và lưu lại kích thước lớn nhất tạm thời (tức temp++). Còn nếu ô nào có giá trị 0, ta lập tức đổi giá trị các ô cùng hàng trước nó thành giá trị 0, hay cùng cột trên nó. Đoạn giải thuật này giúp ta sẽ xóa đi những ô có giá trị bằng 1 tiếp theo trong chu trình đi (để khỏi phải xét nữa).
- k=(k<temp?;temp;k);

VD:
- Thứ tự xét:
0 1 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 1 1 1 1
0 0 1 1 1 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1

- Khi xét các ô màu xanh dương đều là 1, ta xét tiếp các ô màu xanh lá. Gặp trường hợp có giá trị 0 (có 2 ô là 0). Ta đổi những giá trị trước và trên thành 0 (màu tím)
0 1 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 1 1 1 1
0 0 1 1 1 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1

- Như vậy sau khi xét ô màu đỏ ta có k=2, và sau này sẽ không phải xét các ô màu tím nữa vì đã đổi giá trị thành 0.

0 1 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 1 1 1 1
0 0 1 1 1 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1

- Bởi ta có xét các ôđó thì kết quả cho kích thước lớn nhất cũng chỉ nhỏ hơn hoặc bằng k vừa tính được. Ví dụ sau ta chọn ô đỏ để xét, ta cũng chỉ xét được với những ô màu xanh dương là tạo thành hình vuông, còn những ô màu xanh lá thì không tạo được (vì có một ô có giá trị 0).

0 1 0 0 0 0 0 0 0 0
1 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 1 1 1 1
0 0 1 1 1 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
3. Cứ như vậy xét hết ma trận 7*9, cuối cùng ta sẽ có được kích thước lớn nhất.

Ý mình là vậy, giải thuật này đã giảm phần nào một số ô không phải xét.
Anh em góp ý thử nha, mình không có thời gian cài đặt chạy thử.

[NT_OnlyLove]

Còn nếu ô nào có giá trị 0, ta lập tức đổi giá trị các ô cùng hàng trước nó thành giá trị 0, hay cùng cột trên nó. Đoạn giải thuật này giúp ta sẽ xóa đi những ô có giá trị bằng 1 tiếp theo trong chu trình đi (để khỏi phải xét nữa).

Ý tưởng của bạn cũng gần giống với tôi. Có đôi chỗ rút gọn hơn.
Tuy nhiên bạn cũng không cần phải thay đổi mọi cái đã đi rồi thành 0 đâu.
Như bạn biết khi xét tại tọa độ đỉnh A[i][j] (đỉnh trên bên trái) và bạn đã xác định được kích thước hình vuông là max. Như vậy lần xét tiếp nếu trên một hàng bạn chỉ việc dịch chuyển A[i][j+count] mà thôi.
Để tối ưu thêm bạn tạo một biến Tmp để lưu cái vị trí mà nó gặp 0 lần sau cũng sẽ nhảy luôn đến A[i][j +Tmp+1];
Tức là chúng ta tiến hành nhảy cách luôn.
Nói chung nó vẫn phải là tính toán từng khu vực kết hợp thử sai.
Suy nghĩ vậy.

[Forlorn_hope]

Tuy nhiên bạn cũng không cần phải thay đổi mọi cái đã đi rồi thành 0 đâu.
Như bạn biết khi xét tại tọa độ đỉnh A[i][j] (đỉnh trên bên trái) và bạn đã xác định được kích thước hình vuông là max. Như vậy lần xét tiếp nếu trên một hàng bạn chỉ việc dịch chuyển A[i][j+count] mà thôi.
Để tối ưu thêm bạn tạo một biến Tmp để lưu cái vị trí mà nó gặp 0 lần sau cũng sẽ nhảy luôn đến A[i][j +Tmp+1];
Tức là chúng ta tiến hành nhảy cách luôn.
Nói chung nó vẫn phải là tính toán từng khu vực kết hợp thử sai.
Suy nghĩ vậy.

Có nhất thiết phải như vậy (có tối ưu) ko? Bởi ta thêm biến, vài dòng lệnh nhảy như bạn thì chương trình dễ rối hơn. Cái đó chỉ dành cho những người đã kinh nghiệm rồi. Ở đây ta nên tường thuật từng bước cho các bạn dễ hiểu hơn mà.

[NT_OnlyLove]

Có nhất thiết phải như vậy (có tối ưu) ko? Bởi ta thêm biến, vài dòng lệnh nhảy như bạn thì chương trình dễ rối hơn. Cái đó chỉ dành cho những người đã kinh nghiệm rồi. Ở đây ta nên tường thuật từng bước cho các bạn dễ hiểu hơn mà.

Nếu bài này ngoài dùng các biến index thì mình cũng không phải thêm nhiều lắm. Với lại thêm một biến Flag như vậy thì khỏi phải triển khai các bước update lại các ô thành 0, và vòng lặp cũng không phải chạy lại khi ta đã chạy qua rồi.
Nói chung là trao đổi để đưa ra cách tốt nhất mà bạn.
Mình đồng ý với bạn là cho mọi người hiểu.(Cách hình minh họa của bạn vậy rất là hay, mình không có thời gian nên chỉ nói qua về suy nghĩ riêng).
Hôm trước xem qua nên cũng không có suy nghĩ sâu được và cũng không code được luôn.
Thân.

[rox_rook]

Bài này trước có suy nghĩ lâu lắm, cài đặt thì cũng vất vả kinh khủng, hồi có làm trúng được vài test nhưng vẫn chưa tổng quát lắm. Do làm thấy tốn thời gian quá nên bỏ luôn tới h T_T. Hi vọng lần này giải được hoàn thiện. Ht và Onlylove thử cài đặt xem sao