- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: January, 2017 -
**Competitors who opened the problem**: 261 -
**Competitors who submitted a solution**: 129 -
**Number of correct solutions**: 44 -
**Accuracy (percentage correct vs those who opened)**: 16.86% -
**Average Correct Time**: 39 minutes, 15 seconds.

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.

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.

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- |

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

BFSQ{ 0, 1, 3, 2 } |
Board### |
Directions-RR |

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

BFSQ{ 0, 1, 3, 2, 6 } |
Board### |
Directions-RR |

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

BFSQ{ 0, 1, 3, 2, 6, 5 } |
Board### |
Directions-RR |

And node 6, which goes right to 7:

BFSQ{ 0, 1, 3, 2, 6, 5, 7 } |
Board### |
Directions-RR |

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

BFSQ{ 0, 1, 3, 2, 6, 5, 7, 8 } |
Board### |
Directions-RR |

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"`

int R, C; // Rows and columns of the boards vector <int> BFSQ; // The BFS queue, holds index: r*C + c vector <string> 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 <char> 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!

/* Topcoder SRM 707, D2 500-Pointer StepsConstruct James S. Plank Mon Feb 13 15:27:05 EST 2017 */ #include <string> #include <vector> #include <iostream> #include <cstdio> #include <cstdlib> using namespace std; class StepsConstruct { public: string construct(vector <string> board, int k); }; string StepsConstruct::construct(vector <string> board, int k) { int R, C; // Rows and columns of the boards vector <int> BFSQ; // The BFS queue, holds index: r*C + c vector <string> 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 <char> 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 ""; } |