fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<iostream>
  4. #include<vector>
  5. #include<algorithm>
  6. #define lli long long int
  7. #define gc() getchar_unlocked()
  8. using namespace std;
  9. char arr[1002][1002];
  10. char visited[1002][1002];
  11. void input(lli r,lli c)
  12. {
  13.   for(lli i=0;i<r;i++)
  14.   {
  15.     for(lli j=0;j<c;j++)
  16.     {
  17.        cin>>arr[i][j];
  18.        visited[i][j]='0';
  19.     }
  20.   }
  21. }
  22. void print(lli r,lli c)
  23. {
  24.   for(lli i=0;i<r;i++)
  25.   {
  26.      for(lli j=0;j<c;j++)
  27.      {
  28.         printf("%c",arr[i][j]);
  29.      }
  30.      printf("\n");
  31.   }
  32. }
  33.  
  34. void printv(lli r,lli c)
  35. {
  36.   for(lli i=0;i<r;i++)
  37.   {
  38.      for(lli j=0;j<c;j++)
  39.      {
  40.         printf("%c",visited[i][j]);
  41.      }
  42.      printf("\n");
  43.   }
  44. }
  45. lli olx(lli i,lli j,lli count1,lli r,lli c)
  46. {
  47.   // mx++;
  48.    if(i>=r || j>=c)
  49.      return count1;
  50.    visited[i][j]='1';//mark the cell visited so nxt time i will not have to compute again
  51.    lli x1=0,x2=0,x3=0,x4=0;
  52.    if(j+1<c)//dont cross colm
  53.    {
  54.      if(visited[i][j+1]=='0' && arr[i][j+1]=='.')//move right
  55.      {
  56.        x1=olx(i,j+1,count1+1,r,c);
  57.      }
  58.    }
  59.    if(j-1>=0)
  60.    {
  61.      if(visited[i][j-1]=='0' && arr[i][j-1]=='.')//move left
  62.      {
  63.        x2=olx(i,j-1,count1+1,r,c);
  64.      }
  65.    }
  66.  
  67.    if(i+1<r)//move down
  68.    {
  69.       if(visited[i+1][j]=='0' && arr[i+1][j]=='.')
  70.       {
  71.         x3=olx(i+1,j,count1+1,r,c);
  72.       }
  73.    }
  74.    if(i-1>=0)//move up
  75.    {
  76.      if(visited[i-1][j]=='0' && i-1>=0 && arr[i-1][j]=='.')
  77.      {
  78.        x4=olx(i-1,j,count1+1,r,c);
  79.      }
  80.    }
  81.    return max(max(max(x1,x2),max(x3,x4)),count1);
  82.  
  83. }
  84. lli oprtn(lli r,lli c)
  85. {
  86.   lli z=-1,x=0;
  87.   //chck for each cell can we move
  88.   for(lli i=0;i<r;i++)
  89.   {
  90.     for(lli j=0;j<c;j++)
  91.     {
  92.      if(visited[i][j]=='0' && arr[i][j]=='.')//check weather movement is allowed
  93.      {
  94.        x=olx(i,j,0,r,c);
  95.      }
  96.      else
  97.       visited[i][j]='1';
  98.      if(x>z)
  99.      z=x;
  100.     }
  101.   }
  102.   return z;
  103. }
  104.  
  105.  
  106.  
  107. int main()
  108. {
  109.   lli t;
  110.   scanf("%lld",&t);
  111.   while(t--)
  112.   {
  113.     lli r,c;
  114.     scanf("%lld%lld",&c,&r);
  115.     input(r,c);
  116.     lli ans=oprtn(r,c);
  117.  
  118.     printf("%lld\n",ans);
  119.   }
  120. }
  121.  
Success #stdin #stdout 0s 5108KB
comments (?)
stdin
copy 
2
3 3
###
#.#
###
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######
stdout
copy 
0
8
https://ideone.com/YmD8Cv
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!