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:
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:
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 "";
}
|