位图 (Standard IO)

Description

给出一个大小为n行*m列的矩形位图。该位图的每一个象素点不是白色就是黑色，但是至少有一个象素点是白色。在i行j列的象素点我们称为点（i，j）。两个象素点p1=(i1,j1)和p2=(i2,j2)之间的距离定义如下：

d(p1,p2)=|i1-i2|+|j1-j2|

现在的任务是：对于每一个象素点，计算它到最近的白色点的距离。如果它本身是白色点，距离为0。

Input

【输入格式】

第1行：2个整数n，m（1<=n <=182,1<=m<=182）

接下来n行，每一行有一个长度为m的0/1字符串，描述一行象素点。如果点（i，j）为白色，则值为1，否则值为0。

Output

【输出格式】

共n行，每行有m个整数，数之间用1个空格分开，分别表示对应的象素点距离白色点的距离。

题解

DP啊，看代码吧

代码

var
  f:array[..,..]of longint;
  n,m:longint;
function min(o,p:longint):longint;
begin
  if o<p then exit(o);
  exit(p);
end;

procedure init;
var
  i,j:longint;
  ss:string;
begin
  readln(n,m);
  fillchar(f,sizeof(f),$f);
  for i:= to n do
    begin
      readln(ss);
      for j:= to m do
        if ss[j]='1' then f[i,j]:=;
    end;
end;

procedure main;
var
  x,y,i,j,k:longint;
begin
  for k:= to m+n do
    for i:= to n do
      for j:= to m do
        begin
          y:=min(f[i+,j]+,f[i-,j]+);
          x:=min(f[i,j+]+,f[i,j-]+);
          f[i,j]:=min(f[i,j],min(x,y));
        end;
end;

procedure print;
var
  i,j:longint;
begin
  for i:= to n do
    begin
      for j:= to m do
        write(f[i,j],' ');
      writeln;
    end;
end;

begin
  init;
  main;
  print;
end.