TCCO 2005 Qualification Round 1, 500-Pointer (LandMines)

James S. Plank

Fri Oct 23 11:41:17 EDT 2015

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: 2005
Competitors who opened the problem: 168
Competitors who submitted a solution: 122
Number of correct solutions: 100
Accuracy (percentage correct vs those who opened): 59.5%
Average Correct Time: 22 minutes, 16 seconds.

In case topcoder's servers are down

Here is a description of the problem.

This problem concerns a minesweeper in a grid that contains land mines.
The minesweeper starts at point (0,0), and can only face north, east, west and south.
The minesweeper cannot leave the grid.
There is not a mine at (0,0).
The minesweeper owns a device which will beep if the minesweeper is facing a mine, regardless of how far away that mine is.
The minesweeper's job is to "clear" as many points on the grid as possible. A point is "cleared", if the minesweeper can definitively determine that there is no mine on the grid point.
You are given a map, which is a vector of strings. The j-th character of the i'th element of the vector will be either a '-' or a 'M'. It is a '-' if there is no mine at the grid point, and a 'M' if there is a mine at the grid point.
Your job is to return the number of points that the minesweeper can "clear", while ensuring that the minesweeper doesn't die.
In other words, if the minesweeper is pointing in a direction, and the device is beeping, then the minesweeper cannot travel in that direction unless the minesweeper already knows that the next point in that direction is "clear".
The topcoder constraints are weak -- only dealing with square grids of size 50 or less. You aren't so lucky. For you, the total number of grid elements will be <= 50,000.

The examples

#	Grid	Answer
0	{ "--M", "---", "M--" }	1 - although there are 7 safe cells, the minesweeper's device beeps when the minesweeper is pointed east or south, so the minesweeper cannot move from cell (0,0).
1	{ "-M-", "-M-", "--M" }	3 - now, the minesweeper can travel south, but never east.
2	{ "--M-", "-MM-", "----", "----" }	12 - the minesweeper can get to every safe point except for the one east of (0,0).
3	{ "-----", "--M-M", "-----", "-M---", "---M-" }	21 - the minesweeper can get to every safe point this time, because it's a lucky configuration of mines.

Testing yourself

Standard tests.sh and answers.txt (read the Cryptography problem if you need instruction).

Hints

The key in this problem is to turn the instance of a problem into a directed graph, where there is a node for each square, and an edge from square a to b if the soldier can walk from square a to b without detecting a sensor in that direction.

Then the problem is to identify all of the squares reachable from the first square and count them. You do this with depth-first search. Some of you get confused with the part of the problem statement that says "he will not move onto a square if his sensor beeps when pointed in that direction, unless he has previously visited that square." That doesn't mean that you should put an edge from b to a if there is an edge from a to b. It just says that you can backtrack on your depth first search.

Let's take example zero. Here's the graph:

I'm drawing the mines red, and nodes that you can reach from the starting square yellow. The other nodes are blue. Even though the graph above has edges into the starting node, there are none coming out, so there are no other nodes that you can reach from the starting node. The answer is one.

Here are the other examples. In all of them, you discover the yellow nodes by doing a DFS from the starting node.

Example 1:

Example 2:

Example 3:

Now, how you represent your graph and do the DFS is up to you, but let me discuss some decisions and the impact of these decisions.

Adjacency lists should usually be your first thought, and they are a fine way to implement this problem, but there is some subtlety in creating them. In particular, here is what you don't want to do:

For each node, (i,j) do:
- Check every node left of (i,j). If none of these are mines, then add an edge to (i,j-1).
- Check every node right of (i,j). If none of these are mines, then add an edge to (i,j+1).
- Check every node higher than (i,j). If none of these are mines, then add an edge to (i-1,j).
- Check every node lower than (i,j). If none of these are mines, then add an edge to (i+1,j).

Do you see why this is bad? Its performance is going to be O(cols) for the left/right edges and O(rows) for the up/down edges. That's really bad performance (O(rows*cols(rows+cols))).

Instead make the following observations:

If cell (i,j) has the leftmost mine in its row, then all nodes to its left will have edges to the left.
If cell (i,j) has the rightmost mine in its row, then all nodes to its right will have edges to the right.
Obviously, if there is no mine in a row, then all nodes in the row have edges to their left and right.

You should use those observations to build your adjacency lists efficiently.

You may want to represent a node with a single number -- that way it's easy to store the node on the adjacency list. In fact, were I solving this problem anew, I would probably have two vectors, both of size layout.size()*layout[0].size().

One is of states -- '-' or 'M'. I'll be using this as the visited field of my DFS.
One has adjacency lists -- these are integer vectors.

I'll initialize my states so that states[i] = layout[i/layout[0].size()][i%layout[0].size()].

Then, I'll go add links to the adjacency lists as described above, so that the graph is built.

Then, I'll do a DFS to find the connected component containing node 0. I'll use the states fields for the visited field, changing state to '.' when I visit a node.

Finally, I'll count the '.' states and return the sum.