首页 > 代码库 > POJ 2386 Lake Counting 搜索题解
POJ 2386 Lake Counting 搜索题解
简单的深度搜索就可以了,看见有人说什么使用并查集,那简直是大算法小用了。
因为可以深搜而不用回溯,故此效率就是O(N*M)了。
技巧就是增加一个标志P,每次搜索到池塘,即有W字母,那么就认为搜索到一个池塘了,P值为真。
搜索过的池塘不要重复搜索,故此,每次走过的池塘都改成其他字母,如‘@‘,或者‘#‘,随便一个都可以。
然后8个方向搜索。
#include <stdio.h> #include <vector> #include <string.h> #include <algorithm> #include <iostream> #include <string> #include <limits.h> #include <stack> #include <queue> #include <set> #include <map> using namespace std; const int MAX_N = 101; char pond[MAX_N][MAX_N]; const char VIS = '@'; int N, M; bool P; inline bool isLegal(int r, int c) { return 0<=r && 0<=c && r<N && c<M && pond[r][c] == 'W'; } void getPond(int r, int c) { if (!isLegal(r, c)) return ; P = true; pond[r][c] = VIS; getPond(r+1, c); getPond(r-1, c); getPond(r, c+1); getPond(r, c-1); getPond(r+1, c+1); getPond(r+1, c-1); getPond(r-1, c+1); getPond(r-1, c-1);//eight direction search } int main() { while (~scanf("%d %d", &N, &M)) { getchar(); for (int i = 0; i < N; i++) { gets(pond[i]); } int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { P = false; getPond(i, j); ans += P; } } printf("%d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。