璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


icpc:problems:oil_deposits
problems
名称Oil Deposits
题目编号UVA572
题目链接luogu.com.cn/…
来源UVA
算法分类DFS
难易程度容易

Oil Deposits

想法

普通DFS,需要vis打标记,

代码实现

#include<iostream>
#include<cstring>
using namespace std;
 
int n, m;
char maps[110][110];
bool vis[110][110];
 
void DFS(int x, int y)
{
	for (int xx=-1; xx<=1; xx++)
		for (int yy=-1; yy<=1; yy++)
		{
			if(xx+x < 1 || xx+x > n || yy+y < 1 || yy+y > m)
				continue;
			if(vis[xx+x][yy+y])continue;
			if(maps[xx+x][yy+y] != '@')continue;
			vis[xx+x][yy+y] = true;
			DFS(xx+x, yy+y);
		}
 
	return ;
}
 
int main()
{
	while(cin >> n >> m)
	{
		if(n == 0 && m == 0)
			break;
 
		int cnt = 0;
		memset(vis, false, sizeof(vis));
 
		for (int i = 1; i <= n; ++i) 
			for (int j = 1; j <= m; ++j) 
				cin >> maps[i][j] ;
 
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				if(maps[i][j] == '@')
				{
					if(vis[i][j])continue;
					cnt++;
					DFS(i, j);
				}
			}
		}
 
		cout << cnt << endl;
	}
 
	return 0;
}
/app/www/public/data/pages/icpc/problems/oil_deposits.txt · 最后更改: 2023/02/07 09:25 由 温婕莺