首页 > POJ解题报告 > POJ 1562 Oil Deposits[DFS]

POJ 1562 Oil Deposits[DFS]

题目大意:就是求油田的块数,如果一个小油田位于另一个小油田的周围的小矩形上(周围八个小方格),那么认为这两个油田是连通的,求有多少个这样的连通块。
解题思路:DFS搜索,两重循环遍历矩阵,如果这个节点是油田,就从这一个节点出发进行DFS,DFS过程中要进行标记,DFS返回后意味着发现一个连通块。我觉得BFS也是可以的 [em021]
传送门:POJ 1562 Oil Deposits http://poj.org/problem?id=1562
Problem: 1562 Memory: 184K Time: 0MS Language: C++ Result: Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
 
#define MAX_NUM 110
 
int n, m;
bool flag[MAX_NUM][MAX_NUM];
 
bool CheckValid(int rows, int cols)
{
	return rows >= 0 && rows < n &&
		cols >= 0 && cols < m &&
		flag[rows][cols];
}
 
void DFS(int rows, int cols)
{
	for (int i = 0; i < 8; ++i)
	{
		int x = rows + step[i][0];
		int y = cols + step[i][1];
		if (CheckValid(x, y))
		{
			flag[x][y] = 0;
			DFS(x, y);
		}
	}
}
 
int main(int argc, char **argv)
{
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
 
	int i, j, res;
	char ch;
 
	while (1)
	{
		scanf ("%d %d%*c", &n, &m);
		for (i = 0; i < n; ++i)
		{
			for (j = 0; j < m; ++j)
			{
				flag[i][j] = (getchar() == '@' ? 1 : 0);
			}
			getchar();
		}
		res = 0;
		for (i = 0; i < n; ++i)
		{
			for (j = 0; j < m; ++j)
			{
				if (flag[i][j])
				{
					DFS(i, j);
					++res;
				}
			}
		}
		printf ("%d\n", res);
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> POJ 1562 Oil Deposits[DFS]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: POJ解题报告 标签:
  1. 本文目前尚无任何评论.