here is the link to the problem -
https://www.codechef.com/MARCH20B/problems/ADASHOP2
I would appreciate if someone gives me the code for this problem along with explanation. Thank you.
Printable View
here is the link to the problem -
https://www.codechef.com/MARCH20B/problems/ADASHOP2
I would appreciate if someone gives me the code for this problem along with explanation. Thank you.
Just another zero effort codechef wannabe.
Same MO as last month.
http://forums.codeguru.com/showthrea...e-this-problem
One common approach I suppose is to view the problem as a graph theory problem. The squares are viewed as the vertices of a graph and the possible moves between squares are viewed as the edges of the graph. The objective then is to find the shortest route that visits all vertices.
But thanks to the special structure of the problem there's a simpler solution. It can be solved as a puzzle.
Just start at square (1,1) and you will soon figure out the pattern to follow to cover all black squares. As a hint it takes 1+5+1+5+1+5+2 = 20 moves and you're back at (1,1) where you started. You follow the diagonal and make three rectangular side-trips along the way. The easiest way to turn this into a program is to just store the 20 moves in an array and print it. Out pops a valid route and you get the 99 points. To get the final 1 point you note that since it's a round-trip route you can start anywhere along it and so can reuse the (1,1) route you already have regardless of starting point.
I guess the puzzle approach is the expected solution strategy but since it's completely ad-hoc and leads to a trivial program the educational value is very limited in my view. To improve yourself as programmer you should try the graph approach (and/or investigate why and when the puzzle solution works).