最新消息:点击查看大S的省钱秘笈

POJ 3051 Satellite Photographs C语言版

POJ题解 Slyar 92浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

Description

Farmer John purchased satellite photos of W x H pixels of his farm (1 <= W <= 80, 1 <= H <= 1000) and wishes to determine the largest 'contiguous' (connected) pasture. Pastures are contiguous when any pair of pixels in a pasture can be connected by traversing adjacent vertical or horizontal pixels that are part of the pasture. (It is easy to create pastures with very strange shapes, even circles that surround other circles.)

Each photo has been digitally enhanced to show pasture area as an asterisk ('*') and non-pasture area as a period ('.'). Here is a 10 x 5 sample satellite photo:

..*.....**
.**..*****
.*...*....
..****.***
..****.***

This photo shows three contiguous pastures of 4, 16, and 6 pixels. Help FJ find the largest contiguous pasture in each of his satellite photos.

Input

* Line 1: Two space-separated integers: W and H

* Lines 2..H+1: Each line contains W "*" or "." characters representing one raster line of a satellite photograph.

Output

* Line 1: The size of the largest contiguous field in the satellite photo.

Sample Input

10 5
..*.....**
.**..*****
.*...*....
..****.***
..****.***

Sample Output

16

Slyar:依旧是简单的搜索题,注释就不写了。将矩阵搜索一次,遇到'*'就进行DFS,然后把遇到的'*'都变成'.',因为这样一次搜索一定会把与这个'*'相连的所有点都统计完。

转载请注明:Slyar Home » POJ 3051 Satellite Photographs C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (2)

  1. @David, 呵呵,仔细看看你会发现它是不会超出去的~
    Slyar8年前 (2009-05-14)回复
  2. dfs函数里面是不是要判断i和j有没有超过输入数组范围呢。
    David8年前 (2009-05-13)回复