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

相关文章

Windows 上如果忘记了 MySQL 密码 重置密码的两种方法

《Windows上如果忘记了MySQL密码重置密码的两种方法》:本文主要介绍Windows上如果忘记了MySQL密码重置密码的两种方法,本文通过两种方法结合实例代码给大家介绍的非常详细,感... 目录方法 1:以跳过权限验证模式启动 mysql 并重置密码方法 2:使用 my.ini 文件的临时配置在 Wi

Android实现打开本地pdf文件的两种方式

《Android实现打开本地pdf文件的两种方式》在现代应用中,PDF格式因其跨平台、稳定性好、展示内容一致等特点,在Android平台上,如何高效地打开本地PDF文件,不仅关系到用户体验,也直接影响... 目录一、项目概述二、相关知识2.1 PDF文件基本概述2.2 android 文件访问与存储权限2.

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