Gravatar
lihaoze
积分:1315
提交:357 / 748
这一题看起来似乎是 天使玩偶 那一题的简化版,用树状数组来求解,最劣时间复杂度是 $(nm) \log (nm)$,但是因为用树状数组的方法需要把询问和白点坐标一起存起来排序(满足询问的坐标 $x_i$ 小于等于 点的坐标 $x$ 的条件,树状数组满足了询问的坐标 $y_i$ 小于等于 点的坐标 $y$ 的条件),比较占空间,而且代码比较不容易维护。不过因为这一题本来数据规模就不大,而且所有询问都是连续出现的,用bfs也许是最优解,用树状数组的解法适合解决询问比较稀疏的题目。

Gravatar
Tab↹
积分:190
提交:134 / 335
纯暴力即可上榜

Gravatar
城南花已开
积分:176
提交:83 / 192
暴力广搜62分用了八秒,感谢O2使我

Gravatar
HAC DOG
积分:90
提交:33 / 163
感谢o2

Gravatar
发光二向箔
积分:153
提交:83 / 238
0.0几是怎么做到的?

Gravatar
ZooxTark➲
积分:138
提交:59 / 193
感谢最佳评测机gcc/g++4.8.5(C89|C++98) -O2
P.S.把白点全部存在一个数组里,然后暴搜(一定很慢,不建议使用)。

Gravatar
ムラサメ
积分:1497
提交:377 / 744
5.261 s,史上最慢程序……

Gravatar
云卷云书
积分:573
提交:137 / 289

Gravatar
10001
积分:70
提交:117 / 222
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;
}

题目 32 [POI 1999] 位图
2019-05-29 19:03:08
Gravatar
10001
积分:70
提交:117 / 222
#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;

题目 32 [POI 1999] 位图
2019-05-29 19:02:45
Gravatar
ShallowDream雨梨
积分:1505
提交:425 / 1300
为什么要用搜索啊,模拟水过去不行吗

Gravatar
HtBest
积分:894
提交:237 / 464
开始一直以为从0开始搜,结果T了一堆,后来发现居然可以从1开始找0...

Gravatar
wangbinghai
积分:7
提交:4 / 10
其实这是一个多源最短路的题目
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
int a[200][200];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
queue<int>q,p;
void bfs(){
while(!q.empty()){
int x = q.front(),y = p.front();
q.pop();p.pop();
for(int i = 0; i < 4;i++){
int xx = x + dx[i],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;
q.push(xx);p.push(yy);
}
else{
if(a[xx][yy] > a[x][y] + 1){
a[xx][yy] = a[x][y] + 1;
q.push(xx);p.push(yy);
}
}
}
}
}
}
void input(){
scanf("%d%d", &n, &m);
memset(a,-1,sizeof(a));
for(int i = 1; i <= n; i++){
char s[200];
scanf("%s", s);
for(int j = 0; j < m; j++){
if(s[j] == '1'){
a[i][j+1] = 0;
q.push(i);p.push(j+1);
}
}
}
}
void output(){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)printf("%d ",a[i][j]);
printf("\n");
}
}
void solve(){
bfs();
}
int main(){
freopen("bit.in","r",stdin);
freopen("bit.out","w",stdout);
input();
solve();
output();
}

Gravatar
kZime
积分:1101
提交:334 / 677
BFS
不难,但边界条件卡了我好久。。。
我真是弱啊

Gravatar
FoolMike
积分:5206
提交:1165 / 2240
直接把所有白点加入bfs队列,然后bfs就AC

Gravatar
老师,勿删
积分:322
提交:140 / 292
同时扩展白点,产生新的白点

题目 32 [POI 1999] 位图
2016-01-20 18:26:39
Gravatar
0
积分:1347
提交:432 / 695
这个怎么floodfill啊

Gravatar
啊吧啦吧啦吧
积分:544
提交:169 / 323
水水更健康……

Gravatar
水中音
积分:1266
提交:406 / 833
广搜,水的居然没有一遍过……n和m打错居然过九个点,数据是有多弱

题目 32 [POI 1999] 位图
2014-08-30 17:34:17
Gravatar
雪狼
积分:662
提交:204 / 354
回复 @Lattice :
这种方法还是慢了,更好的方法是队列覆盖