A Pleasant Stroll | Editorial by nikbro12

1. Created a 3d dp and initialised 1st row for every possible positions of alice and bob by 0, but if they are side by side initialise by 1
2.   Run 4 nested loops in which for every possible positions update the value of dp by maximum value reachable in previous row
3.   If they are side by side increase the value by 1
4.   Finally check maximum value in last row

```
// Contributed by Nikhil Agrawal
#include<bits/stdc++.h>
#define ff(i,a,b) for(int i=a;i<b;i++)
#define pi (db)3.14159265358979323846264338327950
#define mod 1000000007
#define MAX 100000
#define ll long long
#define db long double
using namespace std;

int r,c;
string m[55];

//check if (i,j) and (i,k) lie inside matrix

bool check(int i,int j,int k){
    if(i>=1&&i<=r&&j<=c&&j>=1&&k<=c&&k>=1) return true;
    else return false;
}

//all possible coordinates where Alice and Bob might be present in previous row

int dj[] = {0,1,-1,0,0,1,-1,1,-1};
int dk[] = {0,0,0,1,-1,1,-1,-1,1};

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>r>>c;
        ff(i,1,r+1){
            cin>>m[i];
        }
          // dp stores no of possible holding hands moments if Alice and Bob are present at (i,j) and (i,k) respectively.
        int dp[r+5][c+5][c+5];
        memset(dp,-1000000,sizeof(dp));

ff(i,1,c+1){
            ff(j,i+1,c+1){

//initialise the first row 
                if(m[1][i-1]!='#'&&m[1][j-1]!='#'){
                    if(j==i+1)
                    dp[1][i][j] = 1;
                    else dp[1][i][j] = 0;
                }
            }
        }

ff(i,2,r+1){
            ff(j,1,c+1){
                ff(k,j+1,c+1){
                    if(m[i][j-1]=='#'||m[i][k-1]=='#') continue;

// this loop find the maximum no of holding hands moments till previous row .
                    // only consider cells reachable from curr position of alice and Bob
                    ff(p,0,9){
                        int nj=j+dj[p],nk=k+dk[p];
                        if(check(i-1,nj,nk)
                        dp[i][j][k] = max(dp[i][j][k],dp[i-1][nj][nk]);
                    }
                    //if Alice and Bob are present side by side then increase the holding hands moments.
                    if(k==j+1) dp[i][j][k] += 1;
                }
            }
        }
        int ans=-1000000;
        ff(i,1,c+1){
            ff(j,i+1,c+1){
                ans= max(ans,dp[r][i][j]);
            }
        }

if(ans>=0) cout<<ans<<"\n";
        else cout<<"Detour\n"; 
    }
}
```

A Pleasant Stroll | Editorial by nikbro12

Download submission

All caught up!

View submission

Is your resume even shortlisted?