Satellite Photographs

Satellite Photographs

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

这是一个比较经典的基于深搜的水题,（当然对于我这种小白来说还是算得上中等水平），以后有时间我也会自己写一点这种博客,

因为我周围的好多大神都在每天更新博客,我可能做不到（作为学渣的我

。emmm）

说正事 ，这道题目应该说思路也很清晰，首先我们先将图存在一个二维数组并且用一个book[][]二维数组进行标记，出现‘*’的在book[][]中标记为 1 ， 然后在遍历a[][]数组，每当出现 ' * '的时候就对该点进行深搜,(x,y)，那么深搜的目的就是要对以(x,y)为中心，对周围进行搜索，直到出现没有 '*'时停止,（别忘了，我们是用book数组进行标记的,也就是book[x][y]== 0 的时候停止），然后我们用一个sum变量来计数，maxn来更新最大值.

代码如下：

#include<iostream>
#include<cstdio>
using namespace std ;

/*卫星问题 可以用深度优先算法进行解决:
   


*/
int book[1500][1500]; // 用于标记访问过的点(pos ： 点是用二维数组表示的 
 
int sum ;
void dfs(int x ,int y) // 深搜函数  
{
  if(book[x][y]==1)
  {
  
    book[x][y] =0 ; //访问过了 ,标记为0 
      sum++; 
      /*
      从 (x,y) 这个位置 的四个方向进行搜索, 
     
      
      */
    dfs(x,y+1); //从(x,y)右边那个位置搜 
    dfs(x,y-1);//从(x,y)左边那个位置搜 
    dfs(x+1,y);//从(x,y)下边那个位置搜 
    dfs(x-1,y); //从(x,y)上边那个位置搜 
      
  }
  else if(book[x][y]==0)
  return ;
  
}
int main()
{
  int w ,h ;
  int i , j ,k ;
  
  char a[1000][100];
  int max ;
  char con;  
  sum = 0;
  cin>>w>>h;
  /*这个题有个小陷阱
  看好哪个是行，哪个是列 
  h 是行 , w 是列 
  */
   for(i=1;i<=h;i++)
   {
    for(j=1; j<=w ;j++)
    {
      cin>> a[i][j] ;  
      if(a[i][j]=='*')
      {
        book[i][j] = 1 ; //标记 带'*'的位置 
       }
       else
       book[i][j] = 0;
       
     }
    
    
   }
   /* 以上读入数据a[i][j];后
    
  ..*.....**
  .**..*****
  .*...*....
  ..****.***
  ..****.***   
  
  book[i][j]变为 1<=i<=h ;
  ->       0010000011          
  ->       0110011111          
  ->       0100010000          
  ->       0011110111          
  ->       0011110111          
   
   
   */
   max = 0 ; 
   for(i=1;i<=h;i++)
   {
    for(j=1; j<=w ;j++)
    {   
      if(a[i][i]=='*')
     {
      
        sum = 0;
        dfs(i,j);/*从二维数字第一个  '*'  开始深搜*/
        if(sum>=max)//更新最大值 
        max= sum ;
      }
       
     }
    
    
   }
   
   cout<<max;
  
  
  return 0 ;
 }