CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

#### Hybrid View

1. Junior Member
Join Date
Jan 2020
Posts
5

here is the link to the problem -

I would appreciate if someone gives me the code for this problem along with explanation. Thank you.

Originally Posted by gamerrk1004
here is the link to the problem -

I would appreciate if someone gives me the code for this problem along with explanation. Thank you.
Please, post the problem description rather than the link to unknown site!

3. Member
Join Date
Nov 2018
Posts
35

Just another zero effort codechef wannabe.

Same MO as last month.
http://forums.codeguru.com/showthrea...e-this-problem

4. Member +
Join Date
Feb 2017
Posts
536

Originally Posted by gamerrk1004
I would appreciate if someone gives me the code for this problem along with explanation.
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).
Last edited by wolle; March 12th, 2020 at 01:37 AM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•