sudshekhar02
BAN USERCan you please specify the question properly? Do caterpillar's eat leaves that are a multiple of their jump numbers or what?
And what does the 1,241,3*1 .. mean?
int arr[100][100]; // will store the map, presently each edge weight is assumed 0 or 1
int m,n;
bool isOk(int a,int b){
return (a>=0 && a<n && b>=0 && b<m && arr[a][b]!=0);
}
int shortestPath(int startX,int startY,int endX,int endY){
queue< pair< int,int> > q;
q.push(mp(startX,startY));
int dis=[0,0,1,-1];
int disY =[1,-1,0,0];
int dist[100][100];
rep(i,n)
rep(j,m)
dist[i][j]=mod;
dist[startX][startY]=0;
while(!q.empty()){
startX = q.top().first;
startY= q.top().second;
q.pop();
rep(i,4){
a = startX+dis[i];
b = startY +disY[i];
if(isOk(a,b) && dist[a][b] > dist[startX][startY]+1)
{
dist[a][b] = dist[startX][startY];
q.push(mp(a,b));
}
}
}
return dist[endX][endY];
}
IMHO your solution is actually O(mn), since for each word you go through its entire length, which in the worst case can be the set of all characters allowed (i.e. m). hence, the complexity
- sudshekhar02 September 09, 2014