soron
BAN USERHow about this? I am assuming Maze is an object, which has left, right, up, and down links which point to other Maze objects
public bool Explore(Maze m)
{
if (visited.Contains(m))
{
return false;
}
else
{
visited.Add(m);
}
if (m.HasLadder())
{
return true;
}
else
{
if (m.Right.TryMove())
{
if (Explore(m.Right))
{
return true;
}
}
if (m.Left.TryMove())
{
if (Explore(m.Left))
{
return true;
}
}
if (m.Down.TryMove())
{
if (Explore(m.Down))
{
return true;
}
}
if (m.Up.TryMove())
{
if (Explore(m.Up))
{
return true;
}
}
}
return false;
}
The cumulative array of petrol should be > cumulative array of distance for every element
distance array 1 3 2 1 3 5
petrol array 1 2 4 3 3 2
If we start at P1,
Cumulative array for distance = 1 4 6 7 10 15
Cumulative array for petrol = 1 3 7 10 13 15
If we start at P3,
Cumulative array for distance = 2 3 6 11 12 15
Cumulative array for petrol = 4 7 10 12 13 15
So P3 is our answer
Create a cumulative array starting from P1. Traverse the array and find the point (Px), where all elements to right of that
have property such that Pi > Di for all i > x AND
Pj > Dj for all j < x
Px+1 is your answer
otherwise not possible.
One example of not possible is
Distance array 2 8 5 4 1 6 2 2
Petrol array 3 5 7 3 5 3 2 2
How about this one? This one with some optimizations (like caching values of mat[i][j] once calculated can lead to O(MN) solution
public int TotalNumberOfPaths(char [][] mat)
{
TotalNumberOfPathsHelper(mat, 0,0);
}
// total number of Paths from i,j
private int TotalNumberOfPathsHelper(char [][] mat, int i, int j)
{
if (mat[i][j] == 'X') //no Path from here
{
return 0;
}
else if ((i >= M) || (j >= N))
{
return 0;
}
else if ((i == M-1) && (j == N-1))
{
return 1;
}
else
{
return (TotalNumberOfPathsHelper(mat, i+1, j) + TotalNumberOfPathsHelper, i, j+1));
}
}
How about this solution? you keep track of next element, and delete the current one.
public void DeleteList(Node root)
{
Node current = root;
Node next;
while ((current != null) && (current.Next != null))
{
next = current.Next;
current.Dispose();
current = next;
}
current.Dispose();
}
great :)
- soron August 28, 2010