I have been working on http://www.spoj.com/problems/LABYR1/ problem where I basically need to find the diameter of a tree and came up with the following approach initially (pseudo code):
global maxLen;
dfs(node):
arr = []
foreach nbr in node.adjList:
arr.append(dfs(nbr))
(a,b) = getMaxTwoElements(arr)
maxLen = a+b if maxLen<a+b else maxLen
return max(arr)
findDia(root):
maxLen=0
dfs(root)
return maxLen
In simple words, at each node, first get the height of every subtree rooted at its child. Now compare the top 2 of these lengths with a global variable to store the diameter and replace if found to be greater.
Here is the actual code I submitted (in c++):
#include<iostream>
#include<cstring>
#include<cstdio>
#include<deque>
#include<queue>
#include<utility>
#include<vector>
#include<climits>
#include<algorithm>
#include<stack>
using namespace std;
bool debug=false;
class Solver{
int nRow , nCol , x , y ,globalMaxPair;
vector<vector<bool> > grid;
queue<pair<int,int> > q;
bool isFree(int x , int y){
if(x<0 ||x>nRow ||y<0 || y>nCol)
return false;
return grid[x][y];
}
bool isLeaf(int x , int y){
if(!isFree(x,y))
return false;
int count=0;
count += isFree(x+1,y) ? 1 : 0;
count += isFree(x-1,y) ? 1 : 0;
count += isFree(x,y+1) ? 1 : 0;
count += isFree(x,y-1) ? 1 : 0;
return count == 1 ;
}
int getPairwiseMax(int arr[4]){
int max = 0 , val;
for(int i=0;i<4;++i){
for(int j=i+1;j<4;++j){
val = arr[i]+arr[j];
max = max<val ? val : max;
if(debug)cout<<"max pair : "<<arr[i]<<" , "<<arr[j]<<" , "<<val<<endl;
}
}
return max;
}
int getMax(int arr[4]){
int max=0 , val;
for(int i=0;i<4;++i){
val = arr[i];
max = val<max ? max : val ;
}
return max;
}
int dfs(int x , int y , int px , int py){
if(x<0 || x>=nCol || y<0 || y>=nRow || !isFree(x,y)){
return 0;
}
if(debug)cout<<"DFS on "<<x<<","<<y<<" from "<<px<<","<<py<<endl;
int a , b , c , d;
a = x-1==px && y==py ? 0 : dfs(x-1,y,x,y);
b = x+1==px && y==py ? 0 : dfs(x+1,y,x,y);
c = x==px && y-1==py ? 0 : dfs(x,y-1,x,y);
d = x==px && y+1==py ? 0 : dfs(x,y+1,x,y);
int arr[4] = {a,b,c,d};
int max = getMax(arr)+1;
int maxPair = getPairwiseMax(arr);
globalMaxPair = globalMaxPair<maxPair ? maxPair : globalMaxPair;
if(debug)cout<<"returning with "<<max<<" from "<<x<<","<<y<<"p("<<px<<","<<py<<")"<<" , globalMaxPair : "<<globalMaxPair<<endl;
return max;
}
public:
Solver(int c , int r):
nRow(r),
nCol(c),
grid(vector<vector<bool> >(r , vector<bool>(c))){
char str[nCol+1];
for(int i=0;i<nRow;++i){
scanf("%s",str);
for(int j=0;j<nCol;++j){
grid[i][j] = str[j]=='.';
}
}
if(debug)cout<<"grid created. Searching for leaf"<<endl;
for(int i=0;i<nRow;++i){
for(int j=0;j<nCol;++j){
if(isLeaf(i,j)){
x=i;
y=j;
if(debug)cout<<"leaf at "<<x<<" , "<<y<<endl;
return;
}
}
}
}
int solve(){
globalMaxPair=0;
dfs(x,y,x,y);
return globalMaxPair ;
}
};
int main(int argc , char **argv)
{
if(argc>1 && strcmp(argv[1],"DEBUG")==0) debug=true;
int t , c , r;
scanf("%d",&t);
while(t--){
scanf("%d %d",&c,&r);
Solver s(c,r);
printf("Maximum rope length is %d.\n",s.solve());
}
return 0;
}
But this gave me Wrong Answer. Now I did a little research on the web and found that the standard way to do this is to do a dfs on any node to get to one of the ends of the diameter and then do another dfs on this end to get the diameter. Here is the code I submitted (in c):
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
typedef long long int lld;
typedef unsigned long long int llu;
int debug=0;
int endX , endY , r , c , maxLen;
char grid[1000][1000];
int getMax(int arr[4]){
int max=0 , val , i;
for(i=0;i<4;++i){
val = arr[i];
max = val<max ? max : val ;
}
return max;
}
int dfs(int x , int y , int len , int px , int py){
if(x>=r || x<0 || y>=c || y<0 || grid[x][y]=='#')
return len;
if(len+1>maxLen){
maxLen = len+1;
endX = x;
endY = y;
}
int l1 = px==x-1 && py==y ? 0 : dfs(x-1,y,len+1,x,y);
int l2 = px==x+1 && py==y ? 0 : dfs(x+1,y,len+1,x,y);
int l3 = px==x && py==y-1 ? 0 : dfs(x,y-1,len+1,x,y);
int l4 = px==x && py==y+1 ? 0 : dfs(x,y+1,len+1,x,y);
int arr[4] = {l1,l2,l3,l4};
int max = getMax(arr)+1;
return max;
}
int main(int argc , char **argv)
{
if(argc>1 && strcmp(argv[1],"DEBUG")==0) debug=1;
int t , i , j , x , y;
scanf("%d",&t);
while(t--){
scanf("%d %d",&c,&r);
for(i=0;i<r;++i){
scanf("%s",grid[i]);
for(j=0;j<c;++j){
if(grid[i][j]=='.'){
x=i;y=j;
}
}
}
endX=-1;endY=-1;maxLen=0;
dfs(x,y,0,x,y);
maxLen=0;
dfs(endX,endY,0,endX,endY);
printf("Maximum rope length is %d.\n",maxLen-1);
}
return 0;
}
This solution got accepted in first attempt itself. So, either the first algorithm is wrong or there is something wrong with the code (apart from being longer than the second one). What is it : algo or code?
