简单的深度搜索就能够了,看见有人说什么使用并查集,那简直是大算法小用了。

由于能够深搜而不用回溯。故此效率就是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;
}

最新文章

  1. [转载]Google Guava官方教程(中文版)
  2. Caf.CMS是一个免费的、 开源,功能齐全的CMS
  3. android 不同dpi图标大小
  4. java生成excel文件
  5. svn: Commit failed (details follow): svn: Authorization failed
  6. 多表头固定demo--html Table
  7. SQL索引学习-索引结构
  8. NFine框架的T4模板
  9. yii2的windows下安装及前期步骤
  10. Spring-boot &amp; spring.security
  11. iOS本地动态验证码生成-b
  12. loadrunner http协议put模式脚本编写
  13. 怎样使CSS3中的animation动画当每滑到一屏时每次都运行
  14. Android 开发笔记“Application 理解”
  15. ASP.NET-FineUI开发
  16. ViewCompat.animate(view) floatEval.evaluate() argbEval.evaluate()
  17. python--学校管理系统(只做了学校管理的接口)
  18. Android-AnsyncTask异步任务
  19. 学号:201621123032 《Java程序设计》第2周学习总结
  20. NAT(Network Address Translation)

热门文章

  1. Windows 的GUID
  2. Ubuntu10.04中利用V4L2读取摄像头数据并保存成文件【转】
  3. IC卡的传输协议(2)-块传输协议T=1续【转】
  4. junit单元测试+junit与Spring结合
  5. Oracle基础 01 表空间 tablespace
  6. 【POI2017||bzoj4726】Sabota?
  7. dubbo消费方超时处理
  8. 表单重置 jQuery
  9. TCP,UDP,IP包头格式及说明(zz)
  10. docker1.13新功能上要关注的点