自动搬运

查看原文

来自洛谷，原作者为

	Jayun 乘骐骥以驰骋兮，来吾道夫先路！

搬运于2025-08-24 21:40:37，当前版本为作者最后更新于2019-06-06 20:52:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

这道题很水，但很适合dp初学者做！（瞎扯一下）

先写动态转移方程，待会解释

$f_{i,j}=min\{f_{i-1,j},f_{i,j-1},f_{i-1,j-1}\}+1$

$(a_{i,j}!=\#)$

解释：

$f_{i,j}$表示以矩阵$i\times j$为右下的正方形边长

用jio指头想想就能知道，$f_{i,j}$是由左、上、左上方向来的

用$min$的原因是，如果用$max$,三个方向的正方形可能会碰到树,以及其它情况（蒟蒻表达不出来，看栗子~）.

拿样例解释：

 . . . . . . . .

 . # . . . # . .

 . . . . . . . .

 . . . . . . . .

 . . . . . . . .

 . . # . . . . .

 . . . . . . . .

 . . . . . . . .

用$max$:

 1 1 1 1 1 1 1 1

 2 0 2 3 4 0 2 3

 3 4 5 6 7 8 9 10

 4 5 6 7 8 9 10 11

 5 6 7 8 9 10 11 12

 6 7 0 9 10 11 12 13

 8 9 10 11 12 13 14 15

 9 10 11 12 13 14 15 16

实际：

 1 1 1 1 1 1 1 1

 1 0 1 2 2 0 1 2

 1 1 1 2 3 1 1 2

（前几行，我累了。。。）

对比一下，用$max$根本不可能

代码

创建美好洛谷，切勿Ctrl+C

c++党这里↓

#inculde<bits/stdc++.h>

using namespace std;

int n,t;
int f[1010][1010];
int ans;

int main() {
   scanf("%d%d",&n,&t);
   for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
           f[i][j]=1;      //边界条件哦
   while(t--)
   {
       int x,y;
       scanf("%d%d",&x,&y);
       f[x][y]=0;           //树的位置打零
   }
   for(int i=1;i<=n;i++)     
   {
       for(int j=1;j<=n;j++) //i和j千万不要从2开始哦
       {
           if(f[i][j]==0)continue;
           f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;          //转移方程哦
           ans=max(ans,f[i][j]);  //更新目标
       }
   }
   printf("%d",ans);      //输出yeah
   return 0;              //。。。yeah
}

p党在这里哦~

var
    f:array[0..1010,0..1010]of longint;//注意是从0开始
    x,y,i,j,n,t,ans:longint;
function min(a,b:longint):longint;
begin
    if a>b then exit(b)
    else exit(a); 
end;
function mx(a,b:longint):longint;
begin
    if a<b then exit(b)
    else exit(a); 
end;
begin
    readln(n,t);
    for i:=1 to n do
        for j:=1 to n do
            f[i,j]:=1;  //边界条件
    for i:=1 to t do
    begin
        readln(x,y);
        f[x,y]:=0;   //树的位置打零
    end;
    for i:=1 to n do
        for j:=1 to n do
        begin
            if f[i,j]=0 then continue;
            f[i,j]:=min(min(f[i-1,j],f[i,j-1]),f[i-1,j-1])+1;   //转移方程
            ans:=max(ans,f[i,j]);  //更新目标
        end;
    writeln(ans);  //yeah~
end.

希望你喜欢（暗示点赞