UVa 572/POJ 1562/HDU 1241 Oil Deposits(DFS,两种写法)

2024-03-05 21:08

本文主要是介绍UVa 572/POJ 1562/HDU 1241 Oil Deposits(DFS,两种写法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

572 - Oil Deposits

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=513

http://poj.org/problem?id=1562

http://acm.hdu.edu.cn/showproblem.php?pid=1241

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil.

A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

Input 

The input file contains one or more grids. Each grid begins with a line containing  m  and  n , the number of rows and columns in the grid, separated by a single space. If  m  = 0 it signals the end of the input; otherwise  $1 \le m \le 100$  and  $1 \le n \le 100$ . Following this are  m  lines of  n  characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either ` * ', representing the absence of oil, or ` @ ', representing an oil pocket.

Output 

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

Sample Input 

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Sample Output 

0
1
2
2

学英语:

Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally.

两个不同的油囊归属于相同的油田iff它们是水平、垂直或斜对地相邻的。


思路:

简单的dfs模板题。


完整代码:

递归:

/*UVaOJ: 0.015s*/
/*POJ: 16ms,164KB*/
/*HDU: 15ms,348KB*/#include <cstdio>
#include <cstring>
using namespace std;int m, n;
bool grid[102][102], vis[102][102];void dfs(int x, int y)
{if (!grid[x][y] || vis[x][y])return;vis[x][y] = true;dfs(x - 1, y - 1);dfs(x - 1, y);dfs(x - 1, y + 1);dfs(x, y - 1);dfs(x, y + 1);dfs(x + 1, y - 1);dfs(x + 1, y);dfs(x + 1, y + 1);
}int main()
{char temp;while (~scanf("%d%d", &m, &n)){if (!m)break;memset(grid, 0, sizeof(grid));memset(vis, 0, sizeof(vis));//下面这个专门对付蛋疼的poj样例,你懂的。while (getchar() == ' ');for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){temp = getchar();if (temp == '@')grid[i][j] = true;}getchar();}int count = 0;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++){if (grid[i][j] && !vis[i][j]){count++;dfs(i, j);}}printf("%d\n", count);}return 0;
}

非递归:(占内存小点)

/*UVaOJ: 0.015s*/
/*POJ: 0ms,160KB*/
/*HDU: 15ms,276KB*/#include <cstdio>
#include <cstring>
using namespace std;struct data
{int x, y;
} queue[20000], now, next;int in, out;
int mov[8][2] = {{ -1, 0}, { -1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, { -1, 1}};
char field[102][102];
int m, n;
int ans;
int k;void bfs(int i, int j)
{in = out = 0;queue[in].x = i;queue[in].y = j;field[i][j] = '*';in++;while (in != out){now = queue[out++];for (k = 0; k < 8; k++){next.x = now.x + mov[k][0];next.y = now.y + mov[k][1];if (field[next.x][next.y] == '@'){field[next.x][next.y] = '*';queue[in++] = next;}}}
}int main()
{int i, j;while (scanf("%d%d", &m, &n), m)//逗号表达式的值是最后一个表达式的值{ans = 0;memset(field, '*', sizeof(field));while (getchar() == ' ');for (i = 1; i <= m; i++)scanf("%s", field[i] + 1);for (i = 1; i <= m; i++)for (j = 1; j <= n; j++)if (field[i][j] == '@'){bfs(i, j);ans++;}printf("%d\n", ans);}
}

Source

Mid-Central USA 1997

这篇关于UVa 572/POJ 1562/HDU 1241 Oil Deposits(DFS,两种写法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/777808

相关文章

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

Win11安装PostgreSQL数据库的两种方式详细步骤

《Win11安装PostgreSQL数据库的两种方式详细步骤》PostgreSQL是备受业界青睐的关系型数据库,尤其是在地理空间和移动领域,:本文主要介绍Win11安装PostgreSQL数据库的... 目录一、exe文件安装 (推荐)下载安装包1. 选择操作系统2. 跳转到EDB(PostgreSQL 的

Docker镜像pull失败两种解决办法小结

《Docker镜像pull失败两种解决办法小结》有时候我们在拉取Docker镜像的过程中会遇到一些问题,:本文主要介绍Docker镜像pull失败两种解决办法的相关资料,文中通过代码介绍的非常详细... 目录docker 镜像 pull 失败解决办法1DrQwWCocker 镜像 pull 失败解决方法2总

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

IDEA中Git版本回退的两种实现方案

《IDEA中Git版本回退的两种实现方案》作为开发者,代码版本回退是日常高频操作,IntelliJIDEA集成了强大的Git工具链,但面对reset和revert两种核心回退方案,许多开发者仍存在选择... 目录一、版本回退前置知识二、Reset方案:整体改写历史1、IDEA图形化操作(推荐)1.1、查看提

Android自定义Scrollbar的两种实现方式

《Android自定义Scrollbar的两种实现方式》本文介绍两种实现自定义滚动条的方法,分别通过ItemDecoration方案和独立View方案实现滚动条定制化,文章通过代码示例讲解的非常详细,... 目录方案一:ItemDecoration实现(推荐用于RecyclerView)实现原理完整代码实现

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

VSCode中C/C++编码乱码问题的两种解决方法

《VSCode中C/C++编码乱码问题的两种解决方法》在中国地区,Windows系统中的cmd和PowerShell默认编码是GBK,但VSCode默认使用UTF-8编码,这种编码不一致会导致在VSC... 目录问题方法一:通过 Code Runner 插件调整编码配置步骤方法二:在 PowerShell

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、