fork download
copy 
  1.     import java.util.ArrayList;
  2.     import java.util.List;
  3.  
  4.     class MineSweeperAlgorithm {
  5.  
  6.         // this minesweeper algorithm uses O(1) space complexity
  7.  
  8.         // set verbose to false to hide the step-by-step loggging
  9.         private static final boolean verbose = false;
  10.         private static int stepCount = 1;
  11.  
  12.         public static void main(String[] args) {
  13.             MineSweeperAlgorithm ins = new MineSweeperAlgorithm();
  14.  
  15.             int[][] matrix;
  16.             // make a test case
  17.             stepCount = 1;
  18.             matrix = new int[5][];
  19.             matrix[0] = new int[]{0, 0, 1, 1, 1};
  20.             matrix[1] = new int[]{0, 1, 1, 1, 1};
  21.             matrix[2] = new int[]{0, 1, 0, 0, 1};
  22.             matrix[3] = new int[]{0, 0, 0, 0, 1};
  23.             matrix[4] = new int[]{0, 0, 0, 0, 1};
  24.  
  25.             // run the test
  26.             System.out.println("Result is " +
  27.                     ins.validate(matrix, matrix.length, matrix[0].length));
  28.             System.out.println();
  29.         }
  30.  
  31.         public boolean validate(int[][] matrix, int m, int n) {
  32.             Pos nextStep = findZero(matrix, m, n);
  33.             if (nextStep == null) {
  34.                 // the matrix deos not contain 0
  35.                 return false;
  36.             }
  37.  
  38.             // visit the first position, and go from there
  39.             matrix[nextStep.x][nextStep.y] = 2;
  40.             while (nextStep != null) {
  41.                 nextStep = step(matrix, nextStep, m, n);
  42.             }
  43.  
  44.             // after visiting all positions, check if there is remaining 0s
  45.             return findZero(matrix, m, n) == null;
  46.         }
  47.  
  48.         Pos step(int[][] matrix, Pos cur, int m, int n) {
  49.             // Now cur is located at a pos with value = 2
  50.             // print matrix in "verbose" mode
  51.             if (verbose) {
  52.                 System.out.println("Step #" + stepCount++);
  53.                 for (int[] array : matrix) {
  54.                     for (int num : array) {
  55.                         System.out.print(num + " ");
  56.                     }
  57.                     System.out.println();
  58.                 }
  59.                 System.out.println();
  60.             }
  61.  
  62.             // make a list of valid neighbors, for the convenience of checking
  63.             List<Pos> neighbors = new ArrayList<Pos>();
  64.             neighbors.add(new Pos(cur.x - 1, cur.y));
  65.             neighbors.add(new Pos(cur.x + 1, cur.y));
  66.             neighbors.add(new Pos(cur.x, cur.y - 1));
  67.             neighbors.add(new Pos(cur.x, cur.y + 1));
  68.             for (int i = neighbors.size() - 1; i >= 0; i--) {
  69.                 if (!isValidPos(neighbors.get(i), m, n)) {
  70.                     neighbors.remove(i);
  71.                 }
  72.             }
  73.  
  74.             // check if there is adjacent 0,
  75.             // if there is, mark 0 as 2 and return that position
  76.             for (Pos neighbor : neighbors) {
  77.                 if (matrix[neighbor.x][neighbor.y] == 0) {
  78.                     matrix[neighbor.x][neighbor.y] = 2;
  79.                     return neighbor;
  80.                 }
  81.             }
  82.  
  83.             // if no adjacent 0, then check if there is adjacent 2.
  84.             // if there is, mark current as 3 and then return that position
  85.             for (Pos neighbor : neighbors) {
  86.                 if (matrix[neighbor.x][neighbor.y] == 2) {
  87.                     matrix[cur.x][cur.y] = 3;
  88.                     return neighbor;
  89.                 }
  90.             }
  91.  
  92.             //if no adjacent 0 and no adjacent 2, mark current as 3 and return null
  93.             matrix[cur.x][cur.y] = 3;
  94.             return null;
  95.         }
  96.  
  97.         boolean isValidPos(Pos p, int m, int n) {
  98.             return p.x >= 0 && p.x < m && p.y >= 0 && p.y < n;
  99.         }
  100.  
  101.         Pos findZero(int[][] matrix, int m, int n) {
  102.             for (int i = 0; i < m; i++) {
  103.                 for (int j = 0; j < n; j++) {
  104.                     if (matrix[i][j] == 0) {
  105.                         return new Pos(i, j);
  106.                     }
  107.                 }
  108.             }
  109.             return null;
  110.         }
  111.  
  112.         class Pos {
  113.             int x;
  114.             int y;
  115.  
  116.             public Pos(int a, int b) {
  117.                 x = a;
  118.                 y = b;
  119.             }
  120.         }
  121.     }
Success #stdin #stdout 0.06s 381184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Result is false
https://ideone.com/3MZ2jo
language:
Java (12.0.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!