fork(1) 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, 0, 1, 0};
  20.         matrix[1] = new int[]{0, 1, 1, 1, 1};
  21.         matrix[2] = new int[]{0, 0, 0, 0, 1};
  22.         matrix[3] = new int[]{0, 1, 1, 0, 1};
  23.         matrix[4] = new int[]{0, 0, 1, 0, 1};
  24.  
  25.         // run the test
  26.         System.out.println("Result is " +
  27.                 ins.validate(matrix));
  28.         System.out.println();
  29.  
  30.         // make another test case
  31.         stepCount = 1;
  32.         matrix = new int[5][];
  33.         matrix[0] = new int[]{0, 0, 0, 1, 0};
  34.         matrix[1] = new int[]{0, 1, 0, 1, 0};
  35.         matrix[2] = new int[]{0, 1, 0, 1, 0};
  36.         matrix[3] = new int[]{0, 1, 0, 1, 0};
  37.         matrix[4] = new int[]{0, 1, 0, 0, 0};
  38.  
  39.         // run the test
  40.         System.out.println("Result is " +
  41.                 ins.validate(matrix));
  42.         System.out.println();
  43.  
  44.         // make another test case
  45.         stepCount = 1;
  46.         matrix = new int[5][];
  47.         matrix[0] = new int[]{0, 0, 0, 1, 0};
  48.         matrix[1] = new int[]{0, 1, 1, 1, 0};
  49.         matrix[2] = new int[]{0, 1, 0, 1, 0};
  50.         matrix[3] = new int[]{0, 0, 0, 1, 0};
  51.         matrix[4] = new int[]{0, 1, 0, 0, 0};
  52.  
  53.         // run the test
  54.         System.out.println("Result is " +
  55.                 ins.validate(matrix));
  56.         System.out.println();
  57.     }
  58.  
  59. 	public boolean validate(int[][] puzzle){//4-connectivity
  60.         boolean firstScan = true;
  61.         for(int r=0;r<puzzle.length;r++){
  62.                 for(int c=0;c<puzzle[0].length;c++){
  63.                         if( 1==puzzle[r][c] )
  64.                                 continue;
  65.                         if( !firstScan && 0==puzzle[r][c])
  66.                                 return false;
  67.  
  68.                         int x = r, y = c;
  69.                         while(true){
  70.                                 while( 0==puzzle[x][y] ){
  71.                                         puzzle[x][y] = 2;
  72.                                         if( x+1<puzzle.length && 0==puzzle[x+1][y] ){
  73.                                                 x += 1;
  74.                                                 continue;
  75.                                         }
  76.                                         if( y+1<puzzle[0].length && 0==puzzle[x][y+1] ){
  77.                                                 y += 1;
  78.                                                 continue;
  79.                                         }
  80.                                         if( x-1>=0 && 0==puzzle[x-1][y] ){
  81.                                                 x -= 1;
  82.                                                 continue;
  83.                                         }
  84.                                         if( y-1>=0 && 0==puzzle[x][y-1] ){
  85.                                                 y -= 1;
  86.                                         }
  87.                                 }
  88.  
  89.                                 while( 2==puzzle[x][y] && !((x+1<puzzle.length && 0==puzzle[x+1][y])|| (y+1<puzzle[0].length && 0==puzzle[x][y+1])
  90.                                                 || (x-1>=0 && 0==puzzle[x-1][y]) || (y-1>=0 && 0==puzzle[x][y-1])) ){
  91.                                         puzzle[x][y] = 3;
  92.                                         if( x+1<puzzle.length && 2==puzzle[x+1][y] ){
  93.                                                 x += 1;
  94.                                                 continue;
  95.                                         }
  96.                                         if( y+1<puzzle[0].length && 2==puzzle[x][y+1] ){
  97.                                                 y += 1;
  98.                                                 continue;
  99.                                         }
  100.                                         if( x-1>=0 && 2==puzzle[x-1][y] ){
  101.                                                 x -= 1;
  102.                                                 continue;
  103.                                         }
  104.                                         if( y-1>=0 && 2==puzzle[x][y-1] ){
  105.                                                 y -= 1;
  106.                                         }
  107.                                 }
  108.  
  109.                                 if(x+1<puzzle.length && 0==puzzle[x+1][y])
  110.                                         x += 1;
  111.                                 else if(y+1<puzzle[0].length && 0==puzzle[x][y+1])
  112.                                         y += 1;
  113.                                 else if(x-1>=0 && 0==puzzle[x-1][y])
  114.                                         x -= 1;
  115.                                 else if (y-1>=0 && 0==puzzle[x][y-1])
  116.                                         y -= 1;
  117.                                 else
  118.                                         break;
  119.                         }
  120.                         firstScan = false;
  121.                 }
  122.         }
  123.         return true;
  124.     }
  125.  
  126. }
  127.  
Success #stdin #stdout 0.06s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Result is false

Result is true

Result is true
https://ideone.com/wmryWn
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!