@aditya_dalal @h_sh
Here’s the solution for the problem Number of City
On a very high level,
First, parse the input to form a tree.
Then, for every node, find the minimum number of days for a vendor to reach that node. This can be done using two DFSes. Output the maximum days among all.
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
#define MAX 1002
vector<int> tree[MAX*MAX];
int n, m, A, B, i, j, k, days[MAX*MAX]={0}, depth[MAX*MAX]={0}, parent[MAX*MAX]={0};
bool vendors[MAX*MAX]={0};
string city[MAX+2];
int treeIndex(int i, int j){
return (i-1)*m + (j+1)/2;
}
/* Parses the input to form a standard tree */
void setTree(int i, int j){
int in = treeIndex(i, j);
if(city[i-1][j] == ' ' && tree[treeIndex(i-1, j)].empty() ){
parent[ treeIndex(i-1, j) ] = in;
tree[in].push_back(treeIndex(i-1, j));
setTree(i-1, j);
}
if(city[i][j+1] == ' ' && tree[treeIndex(i, j+2)].empty()){
parent[ treeIndex(i, j+2) ] = in;
tree[in].push_back(treeIndex(i, j+2));
setTree(i, j+2);
}
if(city[i][j-1] == ' ' && tree[treeIndex(i, j-2)].empty()){
parent[ treeIndex(i, j-2) ] = in;
tree[in].push_back(treeIndex(i, j-2));
setTree(i, j-2);
}
if(city[i][j] == ' ' && tree[treeIndex(i+1, j)].empty()){
parent[ treeIndex(i+1, j) ] = in;
tree[in].push_back(treeIndex(i+1, j));
setTree(i+1, j);
}
//cout<<"Sat "<<in<<endl;
}
void calcDays(int N){
if(vendors[N]){
days[N]=0;
//cout<<N<<"="<<days[N]<<" "<<depth[N]<<"\t";
return;
}
vector<int> :: iterator it;
int cmp, maxx=0;
days[N] = MAX*MAX;
for(it=tree[N].begin(); it!=tree[N].end(); it++){
calcDays(*it);
days[N] = min(days[N], 1+days[*it]);
if(days[*it]>=MAX*MAX)
cmp = 1 + depth[*it];
else
cmp = 0;
maxx = max( maxx, cmp );
}
if(days[N] >=MAX*MAX)
depth[N] = maxx;
//cout<<N<<"="<<days[N]<<" "<<depth[N]<<"\t";
}
int maxAns=0;
int newDays[MAX*MAX]={0};
void getAns(int N){
int profit = 0;
newDays[N] = days[N];
if(parent[N]!=0) // If N is not root then check if the actual value is lesser
newDays[N] = min( days[N], newDays[parent[N]]+1 );
if(vendors[N]){ // If this node is a vender, just return
return;
}
vector<int> :: iterator it;
for(it=tree[N].begin(); it!=tree[N].end(); it++ ){
if(days[*it] >= MAX*MAX){
profit = max(profit, depth[*it]+1);
}
else{
getAns(*it);
}
}
maxAns =max (maxAns, newDays[N]+profit);
//cout<<"at "<<N<<" = "<<maxAns<<endl;
}
int main()
{
int a, b, in;
cin>>n>>m>>A>>B;
getchar();
//cout<<"Caught char\n";
for(i=0; i<=n; i++){
//gets(&city[i]);
getline (cin, city[i]);
}
cin>>k;
for(i=0; i<k; i++){
cin>>a>>b;
in = (a-1)*m + b;
//cout<<"Vendor at "<<in<<endl;
vendors[in] = 1;
}
/* Parse the input to form a tree with parent and children pointers */
setTree(A, B*2-1);
/* Set root to be the initial location of us */
int root = (A-1)*m + B;
/**
* Calculates the depth of each node, and
* Minimum number of days for a vendor to reach every node
* It only gets the rihgt days for the root since we started the dfs from root
* It doens't take into account the cases where it may be possible to get lesser days
for a particular node from a path which includes the root
* Just try to think about what this function is doing and you may understand the problem.
* */
calcDays(root);
/**
* newDays is going to hold the correct number of days for each node for a vender
to reach that node.
**/
newDays[root] = days[root];
/* Do the second DFS to get the correct days and keep track of the maximum among all*/
getAns(root);
cout<<maxAns<<endl;
return 0;
}
