Satellite Photographs(dfs)
发布日期:2021-10-16 05:05:10 浏览次数:2 分类:技术文章

本文共 1972 字,大约阅读时间需要 6 分钟。

Satellite Photographs
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 6092   Accepted: 2874

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

Source


题意:

任意起点,最多能走多少连续的*。

思路:

dfs即可。

代码:

#include
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;char mp[1000][82];bool vis[1000][82];int w,h;int sum,maxx;void dfs(int a,int b)   //ab代表坐标{
       
if(a<0 || a>=h) return;
if(b<0 || b>=w) return;
if(vis[a][b]) return;
if(mp[a][b]=='*')
{
sum++;
vis[a][b]=1;//注意,这是标记的这个点有没有做过起点,所以不用回溯,别混淆
dfs(a-1,b);
dfs(a,b-1);
dfs(a+1,b);
dfs(a,b+1);
}}int main(){
int i,j;
scanf("%d %d",&w,&h);
for(i=0;i
for(j=0;j
 maxx=-1;
for(i=0;i
{
for(j=0;j
{
if(vis[i][j]==0)
{
sum=0;
dfs(i,j);
if(maxx
}
}
}
printf("%d",maxx);
return 0;}


转载地址:https://blog.csdn.net/sinat_37668729/article/details/77070985 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Max Factor(技巧题)
下一篇:Cow Bowling(动态规划)

发表评论

最新留言

做的很好,不错不错
[***.172.111.71]2022年05月22日 08时33分03秒