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
Bài liên quan
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.
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
là hình vuông được vẽ từ điểm đó ra góc phải-trên
ô [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ị.
dựa vào công thức bạn @nguyenvanquan7826 đưa mà làm thôi.
p/s: giống minesweeper nhỉ hehe
Vậy làm sao để có công thức này ạ
quy hoạch động …
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
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Đ
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
P/S: Mọi người tiếp tục nhé, cẩn thận đừng off-topic là được
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
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
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 ô đó.
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ên và biên trái