kuangbin专题 专题一 简单搜索 Oil Deposits HDU - 1241

题目链接:https://vjudge.net/problem/HDU-1241

题意:问有几个油田,一个油田由相邻的‘@’,组成。

思路:bfs,dfs都可以,只需要遍历地图,遇到‘@’,跑一遍搜索,标记跑过的点,然后油田数+1.


 #include <iostream>
#include <cstring>
#include<vector>
#include<string>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
using namespace std; #define inf (1LL << 31) - 1
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--) const int N = ;
int mv[][] = { { , }, { , - }, { , }, { -, },
{ , }, { -, - }, { -, }, { , - } };
char mp[N][N];
bool vis[N][N];
int n, m; struct node{
int x, y;
}; inline void init(){
rep(i, , n) rep(j, , m) vis[i][j] = false;
} inline void input(){ init();
rep(i, , n) rep(j, , m) cin >> mp[i][j];
} inline bool check(int x, int y){
return x >= && x <= n && y >= && y <= m;
} void bfs(int now_x, int now_y){ vis[now_x][now_y] = true; queue<node> que;
que.push(node{ now_x, now_y }); while (!que.empty()){ node tmp = que.front();
que.pop(); rep__(p, , ){
int dx = tmp.x + mv[p][];
int dy = tmp.y + mv[p][]; if (check(dx, dy) && !vis[dx][dy] && mp[dx][dy] == '@'){
vis[dx][dy] = true;
que.push(node{ dx, dy });
}
}
}
} void work(){ int ans = ; rep(i, , n) rep(j, , m){
//附加条件,这个‘@’没被访问过,说明是新的油田的一部分
if (mp[i][j] == '@' && !vis[i][j]){
bfs(i, j);
++ans;
}
} cout << ans << endl;
} int main(){ ios::sync_with_stdio(false);
cin.tie(); while (cin >> n >> m){ if (m == ) break; input();
work();
} return ;
}
上一篇:java:数据结构(二)栈的应用(括号匹配)


下一篇:kuangbin专题 专题一 简单搜索 Fire! UVA - 11624