本文共 730 字，大约阅读时间需要 2 分钟。

问题 R: Lake Counting

时间限制: 1 Sec  内存限制: 128 MB

题目描述

题意：有一块N×M的土地，雨后积起了水，有水标记为‘W’，干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼？

输入

第一行为N,M(1≤N,M≤110)。

下面为N*M的土地示意图。

输出

一行，共有的水洼数。

样例输入

10 12W........WW..WWW.....WWW....WW...WW..........WW..........W....W......W...W.W.....WW.W.W.W.....W..W.W......W...W.......W.

样例输出

3

徐不可说：lake counting 是好久之前在《挑战程序设计竞赛》上看过，后来在oj上a了好多遍的老题目，搜索类水题的代表

#include
   
    using namespace std;int n,m;char a[1000][1000];void dfs(int x,int y){	a[x][y]='.';  //将'w'修改成'.',避免重复搜索	for(int fx=-1;fx<2;fx++)   	for(int fx2=-1;fx2<2;fx2++)  //3*3=9个方向遍历 {	int nx=x+fx,ny=y+fx2;	if(0<=nx&&nx
    
     <=ny&&ny
     
      >n>>m;    for(int i=0;i
      
       >a[i][j];    int res=0;    for(int i=0;i
      
     
    
   

深度搜索的典范！

转载地址：http://hxtgn.baihongyu.com/