HDU-1241 Oil Deposits
搜索 HDU-1241 Oil Deposits
题目链接:杭电1241
题目大意:寻找油田 一个@是有油 @周围8个方向的@视为同一个油田 求给定的区域一共多少个油田
解题思路:首先用BFS 主函数循环找到@ 找到后将坐标传入BFS函数 八个方向遍历 有@就推入队列并把@变为* 一个坐标的八个方向遍历完把队列首项推出 直到队列为空 这BFS函数执行一次就是一个油田 统计函数执行次数并输出
其次用DFS 主函数循环找到@ 找到后将坐标传入DFS函数 八个方向遍历 有@就调取一次DFS函数 最后统计函数执行次数输出
代码块:
//BFS
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
char str[109][109] = { '\0','\0' };
typedef pair<int, int> p;
int xx[8] = { 1,0,-1,0,1,-1,-1,1 };
int yy[8] = { 0,1,0,-1,1,-1,1,-1 };
int m, n;
void bfs(p beginn);
int main() {
while (cin >> m >> n) {
int sc = 0;
if ((m + n) == 0) return 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> str[i][j];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str[i][j] == '@') {
bfs(p(i, j));
sc++;
}
}
}
cout << sc << endl;
}
return 0;
}
void bfs(p beginn) {
queue<p> que;
que.push(beginn);
str[que.front().first][que.front().second] = '*';
while (!que.empty()) {
for (int i = 0; i < 8; i++) {
int x = xx[i] + que.front().first;
int y = yy[i] + que.front().second;
if (x >= 1 && x <= m && y >= 1 && y <= n && str[x][y] == '@') {
str[x][y] = '*';
que.push(p(x, y));
}
}
que.pop();
}
}
//DFS
#include<iostream>
using namespace std;
char str[109][109] = { '\0','\0' };
int xx[8] = { 1,0,-1,0,1,-1,-1,1 };
int yy[8] = { 0,1,0,-1,1,-1,1,-1 };
int m, n;
void dfs(int x,int y);
int main() {
while (cin >> m >> n) {
int sc = 0;
if ((m + n) == 0) return 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> str[i][j];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str[i][j] == '@') {
dfs(i, j);
sc++;
}
}
}
cout << sc << endl;
}
return 0;
}
void dfs(int x, int y) {
str[x][y] = '*';
int px, py;
for (int i = 0; i < 8; i++) {
px = x + xx[i];
py = y + yy[i];
if (px >= 1 && px <= m && py >= 1 && py <= n && str[px][py] == '@') {
void(dfs(px, py));
}
}
return;
}