### James S. Plank

Mon Feb 13 00:02:35 EST 2017

### The Anatomy of a Solution

Obviously, this was a hard one. Perhaps there's an easier way to do it than how I did it, but I gave it 30 seconds of thought at the beginning, and a solution became apparent pretty quickly. The rest was coding, and it took me 30 minutes, because I had to figure out the right information to keep.

Now, let's walk ourselves to the solution before we start writing code. This is clearly a graph problem, which means that we should think about the graph algorithms we've learned:

• Depth-First Search: Maybe -- this seems to involve connectivity.
• Breadth-First Search: This seems better, because if we know the shortest path, we can derive our answer from it.
• Dijkstra's Algorithm: Doesn't matter -- this is not a weighted graph.
• Minimum Spanning Tree -- I've stopped caring. I think Breadth-First Search is going to be a winner.
Now, let's suppose we know the shortest path from the upper left-hand corner to the lower right-hand corner. Call that path P and suppose its length is l. First, if l > k, then we know we can't solve the problem. That's good. Obviously, if l == k, then we have solved the problem. That's also good.

What about when l < k? Suppose that they are both odd or they are both even. Then you can lengthen P by two, by taking the first step along the path, and then going back to the starting position. You can repeat this until l equals k.

What if l is even and k is odd? Then you should see that it's impossible to have a path of length k. Look at the following graph:

 `....`

You should see that any path from the upper left-hand corner to the lower right-hand corner will have an even number of steps. There's no way to get an odd path-length, so if k is odd, then the problem is impossible. Similarly, look at the following graph:

 `......`

Now, you should see that any path from the upper left-hand corner to the lower right-hand corner will have an odd number of steps. There's no way to get an even path-length, so if k is even, then it's impossible.

So, with all cases covered, you have a way to solve the problem:

• Find the shortest path from the upper left-hand corner to the lower right-hand corner. You'll use BFS to do this.
• If the length of this path is greater than i, return "".
• If the length of this path is odd and k is even, return "".
• If the length of this path is even and k is odd, return "".
• While k is greater than the path length, extend the path by two steps by taking the first step along the path, and then going back to the upper-left corner.
• Return the path.

### Coding it up

The reason that this program takes a little while to code is that you have to figure out what data to keep with each node. Here's what I suggest (this is a lot less complex than how I solved it when I first did the problem). For each node, keep a Direction. This is going to be one of 'U', 'D', 'L', 'R' or '-'. You will start by setting each node's Direction to '-'.

When you process a node during the BFS, you'll look in each direction to see if you can step to another node. Suppose you can, and suppose that the node that you can step to is node j. If node j has not been put onto the BFS queue, then you'll push it, and set its Direction to be the direction that you took to get to the node. At the same time, you can change the node's entry on the board to '#', and that way, you won't put the node onto the BFSQ again.

When you reach the final node, you can use its Direction to get to its predecessor on the shortest path. And you can use that node's Direction to get to its predecessor on the shortest path. An so on, until you get to the starting node. While you're doing that, you can store the Directions, and that lets you store the path, so that you can finish the problem.

Let's look at example 1 to illustrate. When you start, you'll push the upper-left node onto the BFSQ and set its entry in board to '#'. We are going to store nodes on the BFSQ as follows. If the node is in row r and column c, then we store r*C+c on the BFSQ, where C is the number of columns in the board. So, after pushing the first node onto the BFSQ, we'll have the following:

 BFSQ{ 0 } Board`#...#....` Directions`---------`

Now, we process node 0. I can go right to node 1 (r=0, c=1), and I can go down to node 3 (r=1, c=0). So, I push them onto the BFSQ and update both Board and Directions. I'm going to color the nodes that I've processed on the BFSQ in red, because in my code, I don't delete them -- I just traverse the BFSQ with an index:

 BFSQ{ 0, 1, 3 } Board`##.##....` Directions`-R-D-----`

Next, we process node 1. We can only go right to node 2, so:

 BFSQ{ 0, 1, 3, 2 } Board`#####....` Directions`-RRD-----`

Next, we process node 3. We can only go down to node 6, so:

 BFSQ{ 0, 1, 3, 2, 6 } Board`#####.#..` Directions`-RRD--D--`

And now, node 2, which goes down to 5:

 BFSQ{ 0, 1, 3, 2, 6, 5 } Board`#######..` Directions`-RRD-DD--`

And node 6, which goes right to 7:

 BFSQ{ 0, 1, 3, 2, 6, 5, 7 } Board`########.` Directions`-RRD-DDR-`

When we process node 5, it goes down to 8:

 BFSQ{ 0, 1, 3, 2, 6, 5, 7, 8 } Board`#########` Directions`-RRD-DDRD`

And finally, processing node 7 doesn't do anything. When we get to node 8, we're done, and we use Directions to define our path back to node zero. The path will be backwards, in this case "DDRR". To get the real path, we reverse it: "RRDD". Its length is 4, and in example 1, we want to get a path of length 12, so we look at the first step of the path -- it's a 'R'. So what we do is put pairs of "RL" on the front of the path until its length is 12:

"RLRLRLRLRRDD"

### Give it a Try

At this point, I'd like you to try programming this up. Here were my variable declarations, including a vector opposite, where opposite[i] holds the opposite direction for i, where i can be one of 'U', 'D', 'L' or 'R'. This helps you extend the path when l < k:

 ``` int R, C; // Rows and columns of the boards vector BFSQ; // The BFS queue, holds index: r*C + c vector Direction; // This holds each node's direction on the shortest path int r, c, i; // Loop variables. int l; // The final path length. string path; // You construct the final path backward and store it here. string rv; // Then you reverse it and return it here. vector opposite; // Opposite(d) is the opposite direction of d. // This helps extend the path to be the right size. ```

The first thing you should try is simply doing the BFS as in the example above, printing out board and Direction at each step. Verify this with example 1 above.

When you're done, create the backward path and print it. You can test for the impossible cases here (example 2 and 3). You can test example 4 as well -- just remember that you're printing the path backward.

Now, extend the path so that l == k. You're still going to print the path backward, but you add steps at the end to make it the right size. Test this with example one -- you should be printing "DDRRLRLRLRLR" or "RRDDUDUDUDUD", depending on whether you pushed node 1 or 3 onto the BFSQ first.

Finally reverse the path and return it. You're done!

### My Solution

My commented solution is below:

 ```/* Topcoder SRM 707, D2 500-Pointer StepsConstruct James S. Plank Mon Feb 13 15:27:05 EST 2017 */ #include #include #include #include #include using namespace std; class StepsConstruct { public: string construct(vector board, int k); }; string StepsConstruct::construct(vector board, int k) { int R, C; // Rows and columns of the boards vector BFSQ; // The BFS queue, holds index: r*C + c vector Direction; // This holds each node's direction on the shortest path int r, c, i; // Loop variables. int l; // The final path length. string path; // You construct the final path backward and store it here. string rv; // Then you reverse it and return it here. vector opposite; // Opposite(d) is the opposite direction of d. // This helps extend the path to be the right size. /* First, set up the opposite vector entries for 'U', 'D', 'L' and 'R'. */ opposite.resize('U'+1); opposite['U'] = 'D'; opposite['D'] = 'U'; opposite['L'] = 'R'; opposite['R'] = 'L'; /* Set R and C, and initialize Direction. */ R = board.size(); C = board[0].size(); Direction.resize(R); for (i = 0; i < R; i++) Direction[i].resize(C, '-'); /* If the upper-left square is not a dot, then it's impossible. */ if (board[0][0] == '#') return ""; /* Push node [0,0] onto the BFSQ, and set its entry in the board to '#'. */ BFSQ.push_back(0); /* Push node 0*C+0 = 0 onto the BFSQ. */ board[0][0] = '#'; /* Now, process the BFSQ. We're going to be pushing nodes onto BFSQ, so its size can increase from iteration to iteration. We don't delete nodes on the BFSQ. */ for (i = 0; i < BFSQ.size(); i++) { r = BFSQ[i]/C; /* Get the row and column of the node from its value in BFSQ */ c = BFSQ[i]%C; /* If it is not the ending node, then check the nodes to the left, right, up and down, and push them onto the BFSQ (setting board and Direction at the same time */ if (r != R-1 || c != C-1) { /* Check the left node. */ if (c > 0 && board[r][c-1] == '.') { BFSQ.push_back((r)*C+c-1); board[r][c-1] = '#'; Direction[r][c-1] = 'L'; } /* Check the right node. */ if (c+1 < C && board[r][c+1] == '.') { BFSQ.push_back((r)*C+c+1); board[r][c+1] = '#'; Direction[r][c+1] = 'R'; } /* Check the upper node. */ if (r > 0 && board[r-1][c] == '.') { BFSQ.push_back((r-1)*C+c); board[r-1][c] = '#'; Direction[r-1][c] = 'U'; } /* Check the lower node. */ if (r+1 < R && board[r+1][c] == '.') { BFSQ.push_back((r+1)*C+c); board[r+1][c] = '#'; Direction[r+1][c] = 'D'; } /* Otherwise, we are at the target node. We need to do a lot here, so I'll go through it in steps. */ } else { /* First, find the path back to the starting node, pushing the directions onto the path vector. This creates the path in reverse. */ while (r != 0 || c != 0) { path.push_back(Direction[r][c]); if (Direction[r][c] == 'L') { c += 1; } else if (Direction[r][c] == 'R') { c -= 1; } else if (Direction[r][c] == 'D') { r -= 1; } else { r += 1; } } /* Set l to be the path length, and return when it's impossible. */ l = path.size(); if (l > k) return ""; if (l % 2 != k % 2) return ""; /* Now, while l is smaller than k, keep doing the opposite of the last step. The path is reversed right now, so this will keep repeating the first step of the path, and then going back to the starting spot. */ while (l < k) { path.push_back(opposite[path[l-1]]); l++; } /* Reverse the path and return it. */ for (i = 0; i < path.size(); i++) rv.push_back(path[path.size()-i-1]); return rv; } } /* If you get here, you couldn't get from the starting node to the ending node. It's impossible */ return ""; } ```