Saturday, October 21, 2017

[Problem3 SPOJ:ROBOTGRI] A problem for lovers of mazes!

PROBLEMhttp://www.spoj.com/problems/ROBOTGRI/

This was a tough nut!

Its a graph problem. Its actually a combination of 2 problems in one! I have voted it as hard and given it my recommendation.

I went through the following resources (none has the actual solution but all serve as hints) to finally come up with a solution for it:

https://www.cs.bu.edu/teaching/alg/maze/
https://www.hackerearth.com/practice/notes/dynamic-programming-problems-involving-grids/
http://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/
http://www.geeksforgeeks.org/count-number-ways-reach-destination-maze/
https://www.youtube.com/watch?v=PwxGTHraMNg&feature=youtu.be
http://www.geeksforgeeks.org/applications-of-breadth-first-traversal/



SOLUTIONhttps://github.com/glassrose/CPP_Problem_Solving/blob/master/SPOJ-ROBOTGRI.cpp
Tested and Accepted: http://www.spoj.com/status/ROBOTGRI,chandniverma/

Time complexity in the worst case: O(n^2 + E)
where n = number of rows (or columns) in the grid
and E = number of edges in the connected graph containing the starting cell 'S'.

Space complexity: O(n^2)

No comments:

Post a Comment