这一题看起来似乎是 天使玩偶 那一题的简化版,用树状数组来求解,最劣时间复杂度是 $(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; }
题目 32 [POI 1999] 位图
2019-05-29 19:03:08
|
|
#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
|
|
为什么要用搜索啊,模拟水过去不行吗
|
|
开始一直以为从0开始搜,结果T了一堆,后来发现居然可以从1开始找0...
|
|
其实这是一个多源最短路的题目
#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(); } |
|
BFS
不难,但边界条件卡了我好久。。。 我真是弱啊 |
|
直接把所有白点加入bfs队列,然后bfs就AC
|
|
同时扩展白点,产生新的白点
题目 32 [POI 1999] 位图
2016-01-20 18:26:39
|
|
这个怎么floodfill啊
|
|
水水更健康……
|
|
广搜,水的居然没有一遍过……n和m打错居然过九个点,数据是有多弱
题目 32 [POI 1999] 位图
2014-08-30 17:34:17
|
|
|