30/09/2018, 16:31

Bài toán lỗ hổng

Cho em hỏi bài này ạ

Cho một bảng gồm M ´ N ô vuông, các ô vuông có cạnh là 1 đơn vị. Một số ô vuông bị loại khỏi bảng, do đó trên bảng có một số lỗ hổng.

Tìm chu vi hình vuông lớn nhất trong bảng mà không có lỗ hổng.

Chẳng hạn, xét bảng 6 ´ 9 có 3 ô vuông bị loại khỏi bảng là các ô ở dòng 2 cột 6, ô ở dòng
3 cột 2, ô ở dòng 5 cột 7 (như hình dưới đây):

Cạnh hình vuông lớn nhất trong bảng trên mà không có lỗ hổng là 4, do đó chu vi cần tìm
là 4´4 = 16.

Dữ liệu:
Cho trong tập tin văn bản BOARD.INP. Dòng đầu là các số nguyên M, N (1 £M, N £ 100)
chỉ số dòng và cột của bảng.
Dòng kế tiếp gồm một số nguyên K duy nhất chỉ số ô vuông bị loại (số lỗ hổng) của bảng.
Trên K dòng tiếp theo, mỗi dòng gồm hai số nguyên tương ứng là chỉ số dòng và cột của ô
vuông bị loại. Chỉ số dòng được đánh số từ 1, tính từ trên xuống dưới trong bảng. Chỉ số
cột được đánh số từ 1, tính từ trái sang phải trong bảng.

Kết quả:
Cho trong tập tin văn bản BOARD.OUT, gồm số nguyên duy nhất là chu vi hình vuông lớn
nhất trong bảng không có lỗ hổng.

Ví dụ:
BOARD.INP                           BOARD.OUT
6 9                                 16
3
2 6
3 2
5 7

Ý tưởng của em là:

- Xét từng ô trong mảng
- Mỗi ô đang xét, nếu không phải là ô lỗ hổng thì mình tăng cạnh thêm 1 (hình vuông)
- Tăng rồi, xét hình vuông vừa có, nếu không có lỗ hổng thì tiếp tục tăng cạnh thêm 1
- Như vậy tới khi tìm có lỗ hổng trong ô vuông, tính và lưu chu vi vào 1 mảng, đem so sánh

Mọi người góp ý và cho ý tưởng khác (nếu được)
Cám ơn mọi người

Quân viết 18:31 ngày 30/09/2018

Mình không hiểu khi bạn tăng cạnh thêm 1 thì tăng cạnh của ô vuông nao?

Mình dùng cách này. Ban đầu bạn cho 2 cạnh trên và trái mỗi ô giá trị là 1 nếu không phải là lỗ hổng. Nếu bất kỳ ô nào là lỗ hổng thì cho giá trị 0. Duyệt mảng 2 chiều, với mỗi ô [i][j] = min([i-1][j-1], [i-1][j], [i][j-1]) + 1.
Cuối cùng chỉ việc tìm max trong ma trận.

nhatlonggunz viết 18:46 ngày 30/09/2018

Hic, em không hiểu, mấy cái 2, 3 là gì vậy anh

@Rok_Hoang anh hướng dẫn cặn kẽ được không

Minh Hoàng viết 18:35 ngày 30/09/2018

là hình vuông được vẽ từ điểm đó ra góc phải-trên

Quân viết 18:40 ngày 30/09/2018

ô [i][j] mang giá trị là ô vuông có cạnh lớn nhất có thể vẽ được tới nó. VD ở ô mang giá trị 4 đó thì từ đó bạn kéo lên bên trên trái sẽ được ô vuông lớn nhất 4 đơn vị.

Minh Hoàng viết 18:41 ngày 30/09/2018

anh hướng dẫn cặn kẽ được không

dựa vào công thức bạn @nguyenvanquan7826 đưa mà làm thôi.
p/s: giống minesweeper nhỉ hehe

nhatlonggunz viết 18:39 ngày 30/09/2018

[i][j] = min([i-1][j-1], [i-1][j], [i][j-1]) + 1

Vậy làm sao để có công thức này ạ

... viết 18:39 ngày 30/09/2018

quy hoạch động …

nhatlonggunz viết 18:47 ngày 30/09/2018

Em đang học quy hoạch động, mà chẳng hiểu gì cả

Kiểu này chắc bị move qua off-topic

Minh Hoàng viết 18:38 ngày 30/09/2018

QHĐ khó mà :)) từ từ thôi. Nhìn bài rồi hình thành cách làm giống tư tưởng QHĐ

Nguyễn Minh Dũng viết 18:33 ngày 30/09/2018

Không off-topic đâu @nhatlonggunz, theo như @nguyenchiemminhvu trả lời thì công thức này tính ra được bằng Quy Hoạch Động. Vì vậy nó vẫn phù hợp với nội dung topic. Trừ phi em hỏi

Quy Hoạch động là gì


P/S: Mọi người tiếp tục nhé, cẩn thận đừng off-topic là được

X viết 18:39 ngày 30/09/2018

cho nguyên mảng bằng 1 rồi set các lỗ hổng bằng 0. Rồi tìm hình vuông “1” lớn nhất :))

  • set mảng ban đầu A[[| giá trị 0 và 1 như trên vừa nói.

  • tạo mảng mới maxsquare[[| sau đó đẩy dòng đầu và cột đầu của mảng A vào. điền các thằng còn lại theo cách: nếu A[i, j| = 1** thì **maxsquare[[| = min(maxsquare[i][j-1], maxsquare[i-1][j], maxsquare[i-1][j-1]) + 1;, nếu bằng 0 thì vẫn bằng 0 :)) ===> được mảng maxsquare[[|

  • tìm giá trị max, trong mảng maxsquare.

  • => chu vi là max x 4

nhatlonggunz viết 18:46 ngày 30/09/2018

Vậy có giống cách của anh Quân trên post 2 không anh.

Dù sao cũng cám ơn mọi người nhiều lắm

X viết 18:41 ngày 30/09/2018

cũng tương tự thôi e nhưng có lẽ dễ hiểu hơn xíu @@ thông cảm bàn phím đang bị liệt vài phím nên gõ cũng có giới hạn

Sáng Béo viết 18:42 ngày 30/09/2018

cũng tương tự thôi e nhưng có lẽ dễ hiểu hơn xíu @@ thông cảm bàn phím đang bị liệt vài phím nên gõ cũng có giới hạn

2 cái y xì nhau mà a. vẫn khó hiểu như nhau, e vẫn ko hiểu tại sao lại xét 3 cái ô đó.

X viết 18:46 ngày 30/09/2018

vào excel và làm cái ma trận cho dễ nhìn rồi suy ngẫm. vì lúc đầu cho vào cái biên trênbiên trái

Bài liên quan
0