?

1.??????? 題目

??????????????? Keke的房子

Description

keke得到了一塊n*m的土地，他灰常高興，于是他想要蓋個(gè)房子，keke的房子必須是正方形的。

但是，并不是土地的每個(gè)地方都能蓋房子。地面上有一些地方不能蓋一磚一瓦。

他當(dāng)然希望將房子蓋得大一些，房子越大就越舒服（有道理沒有？）。

于是他又來惡心你了……

Input

輸入文件第一行為兩個(gè)整數(shù)n,m（1<=n,m<=1000），接下來n行，每行m個(gè)數(shù)字，用空格隔開。0表示該塊土地不能蓋房子，1表示該塊土地完好。

Output

一個(gè)整數(shù)，為keke能蓋出的最大正方形房子的邊長(zhǎng)

Sample Input

4 4

0 1 1 1

1 1 1 0

0 1 1 0

1 1 0 1

Sample Output

2

數(shù)據(jù)范圍

對(duì)于30%的數(shù)據(jù) n,m<=100

對(duì)于100%的數(shù)據(jù) n,m<=1000

?

2.??????? 題目實(shí)質(zhì)

找一個(gè)指定區(qū)域內(nèi)，不經(jīng)過指定區(qū)域的最大的正方形的邊長(zhǎng)。

3.??????? 算法

動(dòng)態(tài)規(guī)劃。

其實(shí)這個(gè)題還有一個(gè)更難的三角形版，也是需要從鄰近的幾個(gè)方向進(jìn)行轉(zhuǎn)移。

用 f[I,j] 存右下點(diǎn)為 I,j 的最大的正方形的邊長(zhǎng)，然后由畫圖 + 手模（手工模擬）得，最大正方形的邊長(zhǎng)應(yīng)為與該格子左邊相鄰、上邊相鄰，或是與他的左上頂點(diǎn)相切的三個(gè)正方形中最小的那個(gè)的邊長(zhǎng) + 1 。

然后，就實(shí)現(xiàn)就行了。

然后三角形版是需要從三個(gè)方向取最小的進(jìn)行轉(zhuǎn)移，然后走一遍正三角形，走一遍倒三角形。

4.??????? 注意事項(xiàng)

這個(gè)題一定要?jiǎng)討B(tài)規(guī)劃，搜索最后兩個(gè)點(diǎn)超時(shí)。

這個(gè)題的手模略。

5.??????? 程序代碼

艾 FHAI? （Pascal）

var

f,a:array[0..1003,0..1003]of longint;

ans,tt,n,i,j,m:longint;

function min(a,b:longint):longint;

begin

if a<b then exit(a);

exit(b);

end;

begin

assign(input,'house.in');reset(input);

assign(output,'house.out');rewrite(output);

readln(n,m);

for i:=1to n do

???? begin

???? for j:=1 to m do

????????? read(a[i,j]);

???? readln;

???? end;

for i:=1 to n do

???? for j:=1 to n do

???? if a[i,j]=1 then

????????? begin

????????? tt:=min(f[i,j-1],f[i-1,j]);

????????? tt:=min(tt,f[i-1,j-1]);

????????? f[i,j]:=tt+1;

????????? if f[i,j]>ans then ans:=f[i,j];

????????? end;

write(ans);

close(input);close(output);

end.

轉(zhuǎn)載于:https://www.cnblogs.com/SueMiller/archive/2011/08/12/2136258.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的解题报告 keke 的房子的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。