For minesweeper algorithm, instead of the most obvious BFS or DFS solution, I want a O(1) space solution.
First of all, I'll explain how the program works. I will pass in a 2D array, with 1 represent mine and 0 represent blank space. The program return true if the map can be opened with single click. Return false if it cannot. Example:
0, 0, 0, 1, 0
0, 1, 1, 1, 1
0, 0, 0, 0, 1
0, 1, 1, 0, 1
0, 0, 1, 0, 1
should return false
0, 0, 0, 0, 0
0, 1, 1, 1, 1
0, 0, 0, 0, 1
0, 1, 1, 0, 1
0, 0, 1, 0, 1
should return true
My algorithm is to visit each 0s and mark as 2. Than from that point, I continue to visit all the 0s and mark as 2. When there's no more 0s, I will visit 2s and then mark 2s as 3s. In the end, all 0s should be marked as 3 if they are inter-connected. Example:
0, 0, 1
0, 1, 1
0, 0, 1
|
v
2, 0, 1
0, 1, 1
0, 0, 1
|
v
2, 2, 1
0, 1, 1
0, 0, 1
|
v
2, 3, 1
0, 1, 1
0, 0, 1
|
v
2, 3, 1
2, 1, 1
0, 0, 1
|
v
2, 3, 1
2, 1, 1
2, 0, 1
|
v
2, 3, 1
2, 1, 1
2, 2, 1
|
v
2, 3, 1
2, 1, 1
2, 3, 1
|
v
2, 3, 1
2, 1, 1
3, 3, 1
|
v
2, 3, 1
3, 1, 1
3, 3, 1
|
v
3, 3, 1
3, 1, 1
3, 3, 1
|
v
return true, since there's no more 0 in the graph
This is my code followed by 3 test cases. Kindly help me review the coding structure/styles or tell me if I have considered all possible test cases. Thanks!
import java.util.ArrayList;
import java.util.List;
public class MineSweeperAlgorithm {
// this minesweeper algorithm uses O(1) space complexity
// set verbose to false to hide the step-by-step loggging
private static final boolean verbose = true;
private static int stepCount = 1;
public static void main(String[] args) {
MineSweeperAlgorithm ins = new MineSweeperAlgorithm();
int[][] matrix;
// make a test case
stepCount = 1;
matrix = new int[5][];
matrix[0] = new int[]{0, 0, 0, 1, 0};
matrix[1] = new int[]{0, 1, 1, 1, 1};
matrix[2] = new int[]{0, 0, 0, 0, 1};
matrix[3] = new int[]{0, 1, 1, 0, 1};
matrix[4] = new int[]{0, 0, 1, 0, 1};
// run the test
System.out.println("Result is " +
ins.validate(matrix, matrix.length, matrix[0].length));
System.out.println();
// make another test case
stepCount = 1;
matrix = new int[5][];
matrix[0] = new int[]{0, 0, 0, 1, 0};
matrix[1] = new int[]{0, 1, 0, 1, 0};
matrix[2] = new int[]{0, 1, 0, 1, 0};
matrix[3] = new int[]{0, 1, 0, 1, 0};
matrix[4] = new int[]{0, 1, 0, 0, 0};
// run the test
System.out.println("Result is " +
ins.validate(matrix, matrix.length, matrix[0].length));
System.out.println();
// make another test case
stepCount = 1;
matrix = new int[5][];
matrix[0] = new int[]{0, 0, 0, 1, 0};
matrix[1] = new int[]{0, 1, 1, 1, 0};
matrix[2] = new int[]{0, 1, 0, 1, 0};
matrix[3] = new int[]{0, 0, 0, 1, 0};
matrix[4] = new int[]{0, 1, 0, 0, 0};
// run the test
System.out.println("Result is " +
ins.validate(matrix, matrix.length, matrix[0].length));
System.out.println();
}
public boolean validate(int[][] matrix, int m, int n) {
Pos nextStep = findZero(matrix, m, n);
if (nextStep == null) {
// the matrix deos not contain 0
return false;
}
// visit the first position, and go from there
matrix[nextStep.x][nextStep.y] = 2;
while (nextStep != null) {
nextStep = step(matrix, nextStep, m, n);
}
// after visiting all positions, check if there is remaining 0s
return findZero(matrix, m, n) == null;
}
Pos step(int[][] matrix, Pos cur, int m, int n) {
// Now cur is located at a pos with value = 2
// print matrix in "verbose" mode
if (verbose) {
System.out.println("Step #" + stepCount++);
for (int[] array : matrix) {
for (int num : array) {
System.out.print(num + " ");
}
System.out.println();
}
System.out.println();
}
// make a list of valid neighbors, for the convenience of checking
List<Pos> neighbors = new ArrayList<Pos>();
neighbors.add(new Pos(cur.x - 1, cur.y));
neighbors.add(new Pos(cur.x + 1, cur.y));
neighbors.add(new Pos(cur.x, cur.y - 1));
neighbors.add(new Pos(cur.x, cur.y + 1));
for (int i = neighbors.size() - 1; i >= 0; i--) {
if (!isValidPos(neighbors.get(i), m, n)) {
neighbors.remove(i);
}
}
// check if there is adjacent 0,
// if there is, mark 0 as 2 and return that position
for (Pos neighbor : neighbors) {
if (matrix[neighbor.x][neighbor.y] == 0) {
matrix[neighbor.x][neighbor.y] = 2;
return neighbor;
}
}
// if no adjacent 0, then check if there is adjacent 2.
// if there is, mark current as 3 and then return that position
for (Pos neighbor : neighbors) {
if (matrix[neighbor.x][neighbor.y] == 2) {
matrix[cur.x][cur.y] = 3;
return neighbor;
}
}
//if no adjacent 0 and no adjacent 2, mark current as 3 and return null
matrix[cur.x][cur.y] = 3;
return null;
}
boolean isValidPos(Pos p, int m, int n) {
return p.x >= 0 && p.x < m && p.y >= 0 && p.y < n;
}
Pos findZero(int[][] matrix, int m, int n) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
return new Pos(i, j);
}
}
}
return null;
}
class Pos {
int x;
int y;
public Pos(int a, int b) {
x = a;
y = b;
}
}
}
The code is also available online for viewing or checking execution result at http://ideone.com/wmryWn
