SPOJ 7188. Escape the Jail (ESJAIL)

   Here is what we will basically do. We need to use BFS and check, every time whenever we are checking a node we need to look over it's neighbors and see if there is one neighbor which we were not able to visit because it is locked we need to push that same node again to the end of the queue so that after our search it is possible that we can unlock the door which we weren't able to visit from the beginning. And we will need some optimizations, we can keep a double element queue where the first element shows the node and the second one shows the "time", whenever the time becomes too much we can exit the process and say that we can'r reach our destination. (in our case too much time can mean that time is more than 2*M). Also we can keep a boolean array which shows the elements we have double pushed to the array because there was a closed neighbor so that we won't have to push the same node many times. Check the source code for a better understanding.

SPOJ 12323. Minimum Knight Moves!!!

http://www.spoj.com/problems/NAKANJ/

 There are lots of ways to solve this, BFS recursion, DFS dynamic. I suggest using thee BFS (If you need more info on BFS go here) approach, it is simpler to understand but harder to implement. Just keep a queue and push the coordinates of the first cell to it, every time you take out an element check all of the 8 neighbors that cell has and add them to the queue , also don't forget to mark all the visited cells so that you won't have to visit them again and again.Check out the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 1841. Prime Path

http://www.spoj.com/problems/PPATH/

   We will solve this with BFS( if you need some more info about BFS go here). First of all we need to find all the prime numbers up to 10000 we can do this easily with the sieve of Eratostenes( for more info about the sieve of Eratostenes go here). We will keep a queue where we will add the number which we have already created , the numbers are always 4 digit which makes our job easier. Now we need to replace all the digits with a different digit from 0 to 9 (be careful while replacing the first digit you might end up replacing the first digit with 0 :) ). Every time when we take out the current number from our queue we need to separate his 4 digits and then keep replacing and combing the digits back to form other numbers, then with the help of the found prime numbers we can check if the number is prime or not, and also don't forget to mark every number you get so that your program won't process the same numbers all over again. Also check the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 13738. Happy Valentine Day (Valentine Maze Game)

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.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 9655. Elevator Trouble

Here is the problem statement
http://www.spoj.com/problems/ELEVTRBL/

This task is solved witha  simple BFS implementation. (For more information about BFS go here). Just keep the list of already visited floors and check if you reached the needed floor stop the BFS else look at all of the neighbours of the current floor( The neighbours are the floors which can be visited from the current floor. NOTE Every floor can't have more than 2 neighbours).

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 6818. Capital City

Here is the problem statement
http://www.spoj.com/problems/CAPCITY/

The graph is directed. (If you need information about directed/indirected graphs go here)/ As you can see from constraints we need to figure out a N*LogN solution or something close to that. The first thing we wanna do is keeping a second graph with reversed edges. We need to loop over all the nodes and run a BFS in the following way. (We are looping over the graph with reversed edges). Initially we keep a mark array for the reversed graph. If the current node is unmarked we start a wave (BFS) from that node (in a reversed graph). If we reached all the edges that means that the current node can be a capital city and we need to launch another wave (BFS) in the initial graph and add all the nodes which are reachable from the current node to the asnwer list. We do the exact opposite( mark it as not capital) if on the reversed graph cannot reach all the nodes.  MAKE SURE TO CHECK THE SOURCE CODE FOR OTHER IMPORTANT DETAILS

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 96. Shopping

Here is the problem statement
http://www.spoj.com/problems/SHOP/

I suggest a way which is not fast enough( you won't be the first in the best solutions field :) ) but works great. This is done by a simple BFS ( you can find information about BFS here) but in a different way (without queue). Initially we keep an array which we will call ans (the array of answers) and the field ans[x][y] will show the minimum cost of getting to the point (x,y) . Initially all the elements are equal to infinity ( to a very larg number which we will call INF). We give our start point the value of 0. Then we loop over our array N*M times ( this is the worst case) and every time we loop we check if the current point we are on is not equal to INF we check its neighbours and update the value if necessary. Then we output the value of ans[x2][y2] where (x2,y2) is the destination point).

       DOWNLOAD THE FULL SOURCE CODE