【HDOJ】3329 The Flood
2024-10-19 11:01:19
超简单BFS。
/* 3329 */
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std; #define MAXN 105 typedef struct node_t {
int x, y;
node_t() {}
node_t(int xx, int yy) {
x = xx; y = yy;
}
} node_t; int n, m, h, total;
int map[MAXN][MAXN];
bool visit[MAXN][MAXN];
int dir[][] = {
-,,,,,-,,
}; inline bool check(int x, int y) {
return x< || x>=n || y< || y>=m;
} void border_bfs(int x, int y) {
int i, j, k;
int xx, yy;
queue<node_t> Q;
node_t nd; Q.push(node_t(x, y));
visit[x][y] = true; while (!Q.empty()) {
nd = Q.front();
Q.pop();
--total;
for (i=; i<; ++i) {
xx = nd.x + dir[i][];
yy = nd.y + dir[i][];
if (check(xx, yy) || visit[xx][yy] || map[xx][yy]>h)
continue;
visit[xx][yy] = true;
Q.push(node_t(xx, yy));
}
}
} void bfs(int x, int y) {
int xx, yy, s;
int i, j, k;
queue<node_t> Q;
node_t nd; Q.push(node_t(x, y));
visit[x][y] = true; while (!Q.empty()) {
nd = Q.front();
Q.pop();
--total;
for (i=; i<; ++i) {
xx = nd.x + dir[i][];
yy = nd.y + dir[i][];
if (check(xx,yy) || visit[xx][yy])
continue;
visit[xx][yy] = true;
Q.push(node_t(xx, yy));
}
}
} int main() {
int t = ;
int i, j, k, tmp;
bool flag;
int maxh; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif while (scanf("%d %d",&n,&m)!=EOF && (n||m)) {
maxh = -;
for (i=; i<n; ++i) {
for (j=; j<m; ++j) {
scanf("%d", &map[i][j]);
if (map[i][j] > maxh)
maxh = map[i][j];
}
}
tmp = n*m;
for (h=; h<maxh; ++h) {
// handle border of map
total = tmp;
memset(visit, false, sizeof(visit));
for (j=; j<m; ++j) {
if (!visit[][j] && map[][j]<=h)
border_bfs(, j);
if (!visit[n-][j] && map[n-][j]<=h)
border_bfs(n-, j);
}
for (i=; i<n; ++i) {
if (!visit[i][] && map[i][]<=h)
border_bfs(i, );
if (!visit[i][m-] && map[i][m-]<=h)
border_bfs(i, m-);
}
// check if there exsits two or more lands
flag = false;
for (i=; i<n; ++i) {
for (j=; j<m; ++j) {
if (!visit[i][j]) {
flag = true;
break;
}
}
if (flag)
break;
}
if (flag) {
bfs(i, j);
if (total > )
break;
}
}
if (h < maxh)
printf("Case %d: Island splits when ocean rises %d feet.\n", ++t, h);
else
printf("Case %d: Island never splits.\n", ++t);
} return ;
}
最新文章
- erlang 200w进程测试
- Windows 通用应用尝试开发 “51单片机汇编”总结
- weed-fs参数列表
- 【Linux】linux常用基本命令
- 《Java编程那点事儿》读书笔记(六)——异常处理
- facebook代码发布
- jquery获得option的值(示例)
- Mvvm Light Toolkit for WPF/Silverlight系列之搭建mvvmlight开发框架
- 字典与集合(Dictionary与Collection)
- Button和ImageButton
- C# 将XML转换成DataSet【转】
- ActionBar点击弹出下拉框操作
- MySQL如何记录binlog
- free 或delete后指针怎么样了
- oracle数据库命令行查看存储过程
- tomcat7启动闪退
- Git坑点——remote: error: GH007: Your push would publish a private email address.
- 12、多线程:Threading、守护线程
- 七、springboot(四)配置redis
- python第二十七课——os模块
热门文章
- docker入门(一)
- Java基础知识强化之集合框架笔记40:Set集合之HashSet存储自定义对象并遍历
- svn 树冲突
- python-集合(第二篇(七):集合)
- 传统的log4j实战
- 给sqlserver配置内存参数
- ssh配置事务
- iOS 常见错误:CALayer position contains NaN: [14 nan]
- C#模拟POST提交表单(二)--HttpWebRequest以及HttpWebResponse
- Sqoop import加载HBase过程中,遇到Permission denied: user=root, access=WRITE, inode=";/user";:hdfs:supergroup:drwxr-xr-x