POJ 2386 Lake Counting 搜索题解
2024-08-28 11:09:09
简单的深度搜索就能够了,看见有人说什么使用并查集,那简直是大算法小用了。
由于能够深搜而不用回溯。故此效率就是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;
}
最新文章
- [转载]Google Guava官方教程(中文版)
- Caf.CMS是一个免费的、 开源,功能齐全的CMS
- android 不同dpi图标大小
- java生成excel文件
- svn: Commit failed (details follow): svn: Authorization failed
- 多表头固定demo--html Table
- SQL索引学习-索引结构
- NFine框架的T4模板
- yii2的windows下安装及前期步骤
- Spring-boot &; spring.security
- iOS本地动态验证码生成-b
- loadrunner http协议put模式脚本编写
- 怎样使CSS3中的animation动画当每滑到一屏时每次都运行
- Android 开发笔记“Application 理解”
- ASP.NET-FineUI开发
- ViewCompat.animate(view) floatEval.evaluate() argbEval.evaluate()
- python--学校管理系统(只做了学校管理的接口)
- Android-AnsyncTask异步任务
- 学号:201621123032 《Java程序设计》第2周学习总结
- NAT(Network Address Translation)