| 题目名称 | 32. [POI 1999] 位图 |
|---|---|
| 输入输出 | bit.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 16 |
| 题目来源 |
 cqw
于2008-04-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：363， 提交：983， 通过率：36.93% | ||||
 瞎拍的 |
100 | 0.000 s | 0.00 MiB | C++ |
 cy |
100 | 0.000 s | 0.00 MiB | C++ |
 Regnig Etalsnart |
100 | 0.000 s | 0.00 MiB | C++ |
 Pine |
100 | 0.000 s | 0.00 MiB | C++ |
 lihaoze |
100 | 0.000 s | 0.00 MiB | C++ |
 521 |
100 | 0.000 s | 0.05 MiB | C++ |
 Hyoi_0Koto |
100 | 0.000 s | 0.05 MiB | C++ |
 DV8 |
100 | 0.002 s | 0.04 MiB | C++ |
 扬帆远洋TEL |
100 | 0.010 s | 1.53 MiB | C++ |
|
Tab↹ |
100 | 0.011 s | 1.83 MiB | C++ |
| 本题关联比赛 | |||
| 2008haoi模拟训练3 | |||
| 皇后 | |||
| 图论练习和一些常规题 | |||
| 图论练习和一些常规题 | |||
| 练习赛 | |||
| 关于 位图 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这一题看起来似乎是 天使玩偶 那一题的简化版，用树状数组来求解，最劣时间复杂度是 $(nm) \log (nm)$，但是因为用树状数组的方法需要把询问和白点坐标一起存起来排序（满足询问的坐标 $x_i$ 小于等于 点的坐标 $x$ 的条件，树状数组满足了询问的坐标 $y_i$ 小于等于 点的坐标 $y$ 的条件），比较占空间，而且代码比较不容易维护。不过因为这一题本来数据规模就不大，而且所有询问都是连续出现的，用bfs也许是最优解，用树状数组的解法适合解决询问比较稀疏的题目。
| ||||
|
纯暴力即可上榜⬇
| ||||
|
暴力广搜62分用了八秒，感谢O2使我水过
| ||||
|
感谢o2
| ||||
|
0.0几是怎么做到的？
| ||||
|
感谢最佳评测机gcc/g++4.8.5(C89|C++98) -O2
P.S.把白点全部存在一个数组里，然后暴搜（一定很慢，不建议使用）。 | ||||
|
5.261 s，史上最慢程序……
| ||||
|
| ||||
|
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; b(0,0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(a[i][j]=='0') o++; } cout<<o<<endl; return 0; }  10001
2019-05-29 19:03
19楼
| ||||
|
#include<bits/stdc++.h>
using namespace std; char a[102][102]; int n,m; void b(int x,int y) { a[x][y]='1'; if((a[x+1][y]=='0'||a[x+1][y]==0)&&x<=n) b(x+1,y); if((a[x-1][y]=='0'||a[x-1][y]==0)&&x>=1) b(x-1,y); if((a[x][y+1]=='0'||a[x][y+1]==0)&&y<=m) b(x,y+1); if((a[x][y-1]=='0'||a[x][y-1]==0)&&y>=1) b(x,y-1); } int main() { freopen("area0.in","r",stdin); freopen("area0.out","w",stdout); int o=0; 10001
2019-05-29 19:02
18楼
| ||||
城南花已开
发光二向箔
ZooxTark➲
云卷云书【问题描述】
给定一个 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) 与离它最近的白像素之间的距离
【样例输入】
3 4 0001 0011 0110
【样例输出】
3 2 1 0 2 1 0 0 1 0 0 1