jzoj 3076. 【备战NOIP2012图论专项模拟试题】位图

发布于 2019-03-30  5 次阅读


题目描述

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

d(p1,p2)=|i1i2|+|j1j2|

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

输入

第1行:2个整数n,m(1<=n <=182,1<=m<=182)

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

输出

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

思路

初值赋为maxlongint,然后进行n+m次简单的dp就可以了,不知道为啥,bfs错了。。。

var
  f,a:array[-1..3000,-1..3000] of longint;
  i,j,k,n,m,s,x,y:longint;
  st:string;
function min(q,w,e,r,t:longint):longint;
begin
  if q
]]>