cogs 32. [POI1999] 位圖

32. [POI1999] 位圖

★   輸入檔案：

bit.in

   輸出檔案：

bit.out

   簡單對比

時間限制：1 s   記憶體限制：128 MB

【問題描述 】

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

【任務 】

編一個程式完成以下操作：

1 ．從輸入檔案中讀入此位圖的有關資訊。

2 ．對于每個像素，計算此像素與離其最近的“白像素”的距離。

3 ．将結果寫到輸出檔案裡面。

【輸入格式 】

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

【輸出格式 】

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

【樣例輸入】

bit.in

3 4 

0001 

0011 

0110

【樣例輸出】

bit.out

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[200][200];
int dx[5]={0,1,0,-1};
int dy[5]={1,0,-1,0};
queue<int>que,pue;
void bfs(){
    while(!que.empty()){
        int x=que.front(),y=pue.front();
        que.pop();
        pue.pop();
        for(int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]!=0 ){
                if(a[xx][yy]==-1){
                    a[xx][yy]=a[x][y]+1;
                    que.push(xx);
                    pue.push(yy);
                }
                else{
                    if(a[xx][yy]>a[x][y]+1){
                        a[xx][yy]=a[x][y]+1;
                        que.push(xx);
                        pue.push(yy);
                    }
                }
            }
            /*cout<<"******************************"<<endl;
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++)
                    printf("%d ",a[i][j]);
                printf("\n");
            }
            cout<<"*******************************"<<endl;*/
        }
    }
}
int main(){
    freopen("bit.in","r",stdin);
    freopen("bit.out","w",stdout);
    scanf("%d%d",&n,&m);
    memset(a,-1,sizeof(a));
    for(int i=1;i<=n;i++){
        char s[200];
        scanf("%s",s+1);
        for(int j=1;j<=m;j++){
            if(s[j]=='1'){
                a[i][j]=0;
                que.push(i);
                pue.push(j);
            }
        }
    }
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }
}      

細雨斜風作曉寒。淡煙疏柳媚晴灘。入淮清洛漸漫漫。 雪沫乳花浮午盞，蓼茸蒿筍試春盤。人間有味是清歡。