Advertisement
Guest User

Untitled

a guest
Apr 26th, 2012
270
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cstdlib>
  6. using namespace std;
  7. const int maxn = 1001;
  8.  
  9. bool v[maxn][maxn];
  10.  
  11. int ans = 0;
  12.  
  13. int findlongest(int i ,int j )
  14. {
  15.     if(v[i][j]==0)return 0;
  16.     v[i][j]=0;
  17.     int maxans = 0;
  18.     vector<int> vv;
  19.     int temp;
  20.     if(v[i-1][j])
  21.     {
  22.         temp = findlongest(i-1, j);
  23.         if(temp!=0)vv.push_back(temp);
  24.     }
  25.     if(v[i][j-1])
  26.     {
  27.         temp = findlongest(i, j-1);
  28.         if(temp!=0)vv.push_back(temp);
  29.     }
  30.     if(v[i+1][j])
  31.     {
  32.         temp = findlongest(i+1, j);
  33.         if(temp!=0)vv.push_back(temp);
  34.     }
  35.     if(v[i][j+1])
  36.     {
  37.         temp = findlongest(i, j+1);
  38.         if(temp!=0)vv.push_back(temp);
  39.     }
  40.     sort(vv.begin(),vv.end());
  41.     for( int k = vv.size()-1;k>=0 && vv.size()-k>=2;k--)
  42.         maxans+=vv[k];
  43.     ans=max(ans,maxans+1);
  44.     if(!vv.size())return 1;
  45.     return vv[vv.size()-1]+1;
  46. }
  47. #define get(i) scanf("%c",&i);
  48.  
  49. int main()
  50. {
  51.     freopen("input.txt", "r", stdin);
  52.     freopen("output.txt","w",stdout);
  53.        // memset(v,false,sizeof(v));
  54.         int i,j;
  55.         char c;
  56.         int n ,m;
  57.     cin>>n>>m;
  58.         int k , t;
  59.         for(i = 0 ;i<m;i++)
  60.             for(j = 0;j<n;j++)
  61.             {
  62.                 cin>>c;
  63.                 if(c == '.')v[i][j]=true;
  64.             }
  65.        
  66.         for(j = 0;j<n;j++)
  67.             for(i = 0 ;i<m;i++)
  68.                 if(v[i][j]){k = i;t = j;break;}
  69.        
  70.         ans = max(ans,findlongest(k,t));
  71.         cout<<ans-1<<endl;
  72.     return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement