簡單的廣搜題，從每個白像素開始向外廣搜，如果新的路徑距離比原來的距離小，更新原來的距離。

/* 
 * Problem: POI1999 bit
 * Author: Guo Jiabao
 * Time: 2008.12.10 16:13:20
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAX=183;
const int INF=0x7FFFFFFF;
const int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};

struct point
{
    int x,y;
};

int N,M,Head,Tail;
int dist[MAX][MAX],bit[MAX][MAX];
point Que[MAX*MAX];

void init()
{
    int i,j,c;
    freopen("bit.in","r",stdin);
    freopen("bit.out","w",stdout);
    scanf("%d%d",&N,&M);
    Head=0;Tail=-1;
    for (i=1;i<=N;i++)
    {
        for (j=1;j<=M;j++)
        {
            dist[i][j]=INF;
            c=getchar();
            while (c==10 || c==13) c=getchar();
            bit[i][j]=c-'0';
            if (c=='1')
            {
                Que[++Tail].x=i;
                Que[Tail].y=j;
                dist[i][j]=0;
            }
        }
    }
}

void BFS()
{
    point i,j;
    int k;
    while (Head<=Tail)
    {
        i=Que[Head++];
        for (k=0;k<4;k++)
        {
            j.x=i.x+dx[k]; j.y=i.y+dy[k];
            if (1<=j.x && j.x <=N && 1<=j.y && j.y<=M && dist[i.x][i.y]+1<dist[j.x][j.y])
            {
                dist[j.x][j.y]=dist[i.x][i.y]+1;
                Que[++Tail]=j;
            }
        }
    }
}

void print()
{
    int i,j;
    for (i=1;i<=N;i++)
    {
        for (j=1;j<=M;j++)
            printf("%d ",dist[i][j]);
        putchar('n');
    }
}

int main()
{
    init();
    BFS();
    print();
    return 0;
}

<h2><span class="mw-headline">位圖</span></h2>

【問題描述 】

給定一個 n*m 的矩形位圖，位圖中的每個像素不是白色就是黑色，但至少有一個是白色的。第 i 行、第 j 列的像素被稱作像素 (i, j) 。兩個像素 p1 = (i1, j1) ， p2 = (i2, j2) 之間的距離定義爲： d(p1, p2) = |i1 - i2| + |j1 - j2|.

【 任務 】

編一個程序完成以下操作：
<ol>
    <li>從輸入文件中讀入此位圖的有關信息。</li>
</ol>
<ol>
    <li>對於每個像素，計算此像素與離其最近的“白像素”的距離。</li>
</ol>
<ol>
    <li>將結果寫到輸出文件裏面。</li>
</ol>
【輸入格式 】

輸入文件的第一行包含兩個整數 n, m （ 1 ≤ n ≤ 182, 1 ≤ m ≤ 182 ），用一個空格隔開。接下來 n 行，每一行都包含一個長度爲 m 的 01 串；第 i+1 行，第 j 列的字符若爲 1 ，則像素 (i, j) 是白色的；否則是黑色的。

【輸出格式 】

輸出文件包含 n 行 , 每行有 m 個用空格隔開的整數。第 i 行、第 j 列的整數表示 (i, j) 與離它最近的白像素之間的距離

【樣例輸入】
<pre>3 4
0001
0011
0110</pre>
【樣例輸出】
<pre>3 2 1 0
2 1 0 0
1 0 0 1</pre>