超简单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 ;
}

最新文章

  1. erlang 200w进程测试
  2. Windows 通用应用尝试开发 “51单片机汇编”总结
  3. weed-fs参数列表
  4. 【Linux】linux常用基本命令
  5. 《Java编程那点事儿》读书笔记(六)——异常处理
  6. facebook代码发布
  7. jquery获得option的值(示例)
  8. Mvvm Light Toolkit for WPF/Silverlight系列之搭建mvvmlight开发框架
  9. 字典与集合(Dictionary与Collection)
  10. Button和ImageButton
  11. C# 将XML转换成DataSet【转】
  12. ActionBar点击弹出下拉框操作
  13. MySQL如何记录binlog
  14. free 或delete后指针怎么样了
  15. oracle数据库命令行查看存储过程
  16. tomcat7启动闪退
  17. Git坑点——remote: error: GH007: Your push would publish a private email address.
  18. 12、多线程:Threading、守护线程
  19. 七、springboot(四)配置redis
  20. python第二十七课——os模块

热门文章

  1. docker入门(一)
  2. Java基础知识强化之集合框架笔记40:Set集合之HashSet存储自定义对象并遍历
  3. svn 树冲突
  4. python-集合(第二篇(七):集合)
  5. 传统的log4j实战
  6. 给sqlserver配置内存参数
  7. ssh配置事务
  8. iOS 常见错误:CALayer position contains NaN: [14 nan]
  9. C#模拟POST提交表单(二)--HttpWebRequest以及HttpWebResponse
  10. Sqoop import加载HBase过程中,遇到Permission denied: user=root, access=WRITE, inode=&quot;/user&quot;:hdfs:supergroup:drwxr-xr-x