位圖 (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.