The problem statement
So, this task really requires a good approach. First of all a simple brute force approach won't pass for sure , for n=5 and m=5 it already gives a time limit exceeded error. So here is how we will do it.
Let's look on this example so that it can be easier to understand
3 6
C#C###
OTOV#
######
Its a little bit different then the example in spoj , but I wrote it this way so that it can be an understandable table, in here "T" is the starting point, "V" is the ending point , "O" is a simple walkable area and # is the wall. we are going to use BFS and DFS . First of all we need to know every distance between the cells which we need ( cells which are "C , "V" or "T") . We need to find the distances between every pair and then make a special graph. OK, so here is the main thing, we need a BFS function which will count the distance between the given cell and all other "important" cells. (We call a cell "important' if it is either a chocolate or a stating or ending point). Let us give the starting point the index of 1 in our graph and the ending point the index 12 in our graph and all the chocolates from indexes 2 to 11. So, in the example I showed above we will have the graph below.
As you can see in the picture, I wrote the coordinate of the node which comes from the initial array (for example the starting point which we gave an index of 1 has a coordinate in the given array of (2,2 ) ). The red numbers are the distances between the 2 pairs (for example the distance between the starting point and the chocolate in the cell (1,3) is 2). Here is another NOTE , if on our BFS we weren't able to get to at least one "important" cell that means that the answer is "Mission Failed!".
Now, after we built out graph we need to find the best way. Here we can just do a recursive brute force (taking every single possibility) which passes over all the chocolates and pick the best answer.
Here is a little optimization which got me accepted as I was getting a TLE without it. We need to keep the answer in some variable, let's call it ANS. Initially ANS equals to a large number. Whenever we have passed over all the nodes we need to update our answer. So here is the optimization, If at some point in the middle of our recursion our already passed distance is larger then the ans and we still didn't get to the end we can brake that recursion because there is no way we are going to get a better answer. Make sure to check teh source code for other little details and overall understanding.
So, this task really requires a good approach. First of all a simple brute force approach won't pass for sure , for n=5 and m=5 it already gives a time limit exceeded error. So here is how we will do it.
Let's look on this example so that it can be easier to understand
3 6
C#C###
OTOV#
######
Its a little bit different then the example in spoj , but I wrote it this way so that it can be an understandable table, in here "T" is the starting point, "V" is the ending point , "O" is a simple walkable area and # is the wall. we are going to use BFS and DFS . First of all we need to know every distance between the cells which we need ( cells which are "C , "V" or "T") . We need to find the distances between every pair and then make a special graph. OK, so here is the main thing, we need a BFS function which will count the distance between the given cell and all other "important" cells. (We call a cell "important' if it is either a chocolate or a stating or ending point). Let us give the starting point the index of 1 in our graph and the ending point the index 12 in our graph and all the chocolates from indexes 2 to 11. So, in the example I showed above we will have the graph below.
As you can see in the picture, I wrote the coordinate of the node which comes from the initial array (for example the starting point which we gave an index of 1 has a coordinate in the given array of (2,2 ) ). The red numbers are the distances between the 2 pairs (for example the distance between the starting point and the chocolate in the cell (1,3) is 2). Here is another NOTE , if on our BFS we weren't able to get to at least one "important" cell that means that the answer is "Mission Failed!".
Now, after we built out graph we need to find the best way. Here we can just do a recursive brute force (taking every single possibility) which passes over all the chocolates and pick the best answer.
Here is a little optimization which got me accepted as I was getting a TLE without it. We need to keep the answer in some variable, let's call it ANS. Initially ANS equals to a large number. Whenever we have passed over all the nodes we need to update our answer. So here is the optimization, If at some point in the middle of our recursion our already passed distance is larger then the ans and we still didn't get to the end we can brake that recursion because there is no way we are going to get a better answer. Make sure to check teh source code for other little details and overall understanding.
No comments:
Post a Comment