fork(2) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int labyrinth(vector<vector<char>>,vector<vector<int>>&,int a,int b);
  4. int main()
  5. {
  6.     int tc,c,r,i,j,k,fans,temp;
  7.     string str;
  8.     cin>>tc;
  9.     for(i=0;i<tc;i++){
  10.         fans=0;
  11.         cin>>c>>r;
  12.         vector<vector<char>> arr(r,vector<char> (c));
  13.         vector<vector<int>> ans(r,vector<int> (c,-1));
  14.         for(j=0;j<r;j++){
  15.                 cin>>str;
  16.             for(k=0;k<c;k++){
  17.                 arr[j][k]=str[k];
  18.             }
  19.         }
  20.         for(j=0; j<r; j++)
  21.             for(k=0; k<c; k++){
  22.                 if(arr[j][k]=='.' && ans[j][k]==-1){
  23.                     temp=labyrinth(arr,ans,j,k);
  24.                     if(temp>fans)
  25.                         fans=temp;
  26.                 }
  27.             }
  28.             if(fans-1==-1)
  29.                 cout<<"Maximum rope length is 0."<<endl;
  30.             else
  31.                 cout<<"Maximum rope length is "<<fans-1<<"."<<endl;
  32.     }
  33.     return 0;
  34. }
  35. int labyrinth(vector<vector<char>> arr,vector<vector<int>> &ans,int a,int b)
  36. {
  37.     vector<int> temp;
  38.     int i,j,value=0,flag;
  39.     stack<pair<int,int>> stk;
  40.     map<pair<int,int>,int> mp;
  41.     stk.push({a,b});
  42.     mp[{a,b}]=value;
  43.     while(!stk.empty()){
  44.         flag=0;
  45.         i=stk.top().first;
  46.         j=stk.top().second;
  47.         value=mp[{i,j}];
  48.         value++;
  49.         ans[i][j]=value;
  50.         stk.pop();
  51.         //top
  52.         if(i-1>=0 && arr[i-1][j]=='.' && ans[i-1][j]==-1){
  53.             stk.push({i-1,j});
  54.             mp[{i-1,j}]=value;
  55.             flag=1;
  56.         }
  57.         //left
  58.         if(j-1>=0 && arr[i][j-1]=='.' && ans[i][j-1]==-1){
  59.             stk.push({i,j-1});
  60.             mp[{i,j-1}]=value;
  61.             flag=1;
  62.         }
  63.         //right
  64.         if(j+1<=arr[0].size()-1 && arr[i][j+1]=='.' && ans[i][j+1]==-1){
  65.             stk.push({i,j+1});
  66.             mp[{i,j+1}]=value;
  67.             flag=1;
  68.         }
  69.         //down
  70.         if(i+1<=arr.size()-1 && arr[i+1][j]=='.' && ans[i+1][j]==-1){
  71.             stk.push({i+1,j});
  72.             mp[{i+1,j}]=value;
  73.             flag=1;
  74.         }
  75.         if(flag==0)
  76.             temp.push_back(value);
  77.     }
  78.     return *max_element(temp.begin(),temp.end());
  79. }
  80.  
Success #stdin #stdout 0s 4308KB
comments (?)
stdin 
2
3 3
###
#.#
###
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######
stdout 
Maximum rope length is 0.
Maximum rope length is 8.
https://ideone.com/BRrMsh
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!