首页 > 代码库 > cogs [POI1999] 位图

cogs [POI1999] 位图

2024-10-08 19:54:39   219人阅读

★   输入文件：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

3 2 1 0
2 1 0 0
1 0 0 1

T   1/3:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cmath>
  5 #include<queue>
  6 #include<cstring>
  7 #include<string>
  8 
  9 using namespace std;
 10 const int N=190;
 11 const int xd[8]={0,0,1,-1};
 12 const int yd[8]={-1,1,0,0};
 13 
 14 struct node{
 15     int x,y,step;
 16 }now,nxt,tim;
 17 
 18 int a[N][N];
 19 int ans[N][N];
 20 bool jud[N][N];
 21 bool vis[N][N];
 22 int n,m;
 23 queue<node>q;
 24 
 25 int read()
 26 {
 27     int x=0;
 28     bool flag=1;
 29     char c=getchar();
 30     while(c<‘0‘||c>‘9‘)c=getchar();
 31     while(c>=‘0‘&&c<=‘9‘&&flag)
 32     {
 33         x=c-‘0‘;
 34         flag=0;
 35     }
 36     return x;
 37 }
 38 
 39 inline void bfs(int x,int y)
 40 {
 41     memset(jud,0,sizeof(jud)); 
 42     while(!q.empty())q.pop();
 43     jud[x][y]=1;
 44     now.x=x;
 45     now.y=y;
 46     now.step=0;
 47     q.push(now);
 48     while(!q.empty())
 49     {
 50         tim=q.front();
 51         q.pop();
 52         for(int i=0;i<4;i++)
 53         {
 54             int xx=tim.x,yy=tim.y;
 55             if(!jud[xx+xd[i]][yy+yd[i]]&&xx+xd[i]>0&&xx+xd[i]<=n&&yy+yd[i]>0&&yy+yd[i]<=m)
 56             {
 57                 int xxx=xx+xd[i];
 58                 int yyy=yy+yd[i];
 59                 jud[xx+xd[i]][yy+yd[i]]=1;
 60                 nxt.x=xx+xd[i];
 61                 nxt.y=yy+yd[i];
 62                 nxt.step=tim.step+1;
 63                 int step=nxt.step;
 64                 if(a[nxt.x][nxt.y]==1)
 65                 {
 66                     ans[x][y]=nxt.step;
 67                     return ;
 68                 }
 69                 q.push(nxt);
 70             }
 71         }        
 72     }    
 73 }
 74 
 75 int main()
 76 {
 77     freopen("bit.in","r",stdin);
 78     freopen("bit.out","w",stdout);
 79     scanf("%d%d",&n,&m);
 80     for(int i=1;i<=n;i++)
 81         for(int j=1;j<=m;j++)
 82             a[i][j]=read();
 83     for(int i=1;i<=n;i++)
 84         for(int j=1;j<=m;j++)
 85         {
 86             if(a[i][j]==1)
 87             {
 88                 ans[i-1][j]=1,vis[i-1][j]=1;
 89                 ans[i+1][j]=1,vis[i+1][j]=1;
 90                 ans[i][j-1]=1,vis[i][j-1]=1;
 91                 ans[i][j+1]=1,vis[i][j+1]=1;
 92             }
 93         }
 94     for(int i=1;i<=n;i++)
 95         for(int j=1;j<=m;j++)
 96             if(!a[i][j]&&!vis[i][j])
 97                 bfs(i,j);
 98 
 99     for(int i=1;i<=n;i++)
100     {
101         for(int j=1;j<=m;j++)
102         {
103             if(!a[i][j])printf("%d ",ans[i][j]);
104             else printf("0 ");
105         }
106         printf("\n");
107     }    
108     return 0;
109 }
110 /*
111 3 4
112 0001
113 0011
114 0110 
115 */

思路果然挺简单：

 

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 using namespace std;
 5 int n,m;
 6 int a[200][200];
 7 int dx[] = {0,1,0,-1};
 8 int dy[] = {1,0,-1,0};
 9 queue<int>q,p;
10 
11 void bfs() 
12 {
13     while(!q.empty()) 
14     {
15         int x = q.front(),y = p.front();
16         q.pop();
17         p.pop();
18         for(int i = 0; i < 4; i++) 
19         {
20             int xx = x + dx[i],yy = y + dy[i];
21             if(xx >= 1 && xx <= n && yy >= 1&& yy <= m && a[xx][yy] != 0 ) 
22             {
23                 if(a[xx][yy] == -1) 
24                 {
25                     a[xx][yy] = a[x][y] + 1;
26                     q.push(xx);
27                     p.push(yy);
28                 } else 
29                 {
30                     if(a[xx][yy] > a[x][y] + 1) 
31                     {
32                         a[xx][yy] = a[x][y] + 1;
33                         q.push(xx);
34                         p.push(yy);
35                     }
36                 }
37             }
38         }
39     }
40 }
41 
42 void input() 
43 {
44     scanf("%d%d", &n, &m);
45     memset(a,-1,sizeof(a));
46     for(int i = 1; i <= n; i++) 
47     {
48         char s[200];
49         scanf("%s", s);
50         for(int j = 0; j < m; j++) 
51         {
52             if(s[j] == ‘1‘) 
53             {
54                 a[i][j+1] = 0;
55                 q.push(i);
56                 p.push(j+1);
57             }
58         }
59     }
60 }
61 
62 void output() 
63 {
64     for(int i = 1; i <= n; i++) 
65     {
66         for(int j = 1; j <= m; j++)printf("%d ",a[i][j]);
67         printf("\n");
68     }
69 }
70 
71 void solve() 
72 {
73     bfs();
74 }
75 int main() {
76     freopen("bit.in","r",stdin);
77     freopen("bit.out","w",stdout);
78     input();
79     solve();
80     output();
81 }

 

cogs [POI1999] 位图


联系
我们