fork download
copy 
  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3. import java.util.Scanner;
  4.  
  5. public class Main {
  6.  
  7.     static class GridPair {
  8.  
  9.         int r;
  10.         int c;
  11.  
  12.         public GridPair(int r, int c) {
  13.             this.r = r;
  14.             this.c = c;
  15.         }
  16.  
  17.     }
  18.  
  19.     private static boolean isBoundary(int X, int Y, int[][] grid) {
  20.  
  21.         int openSpaces = 0;
  22.  
  23.         if(X + 1 <= grid.length - 1 && grid[X+1][Y] == 0) {
  24.             openSpaces++;
  25.         }
  26.  
  27.         if(X - 1 >= 0 && grid[X-1][Y] == 0) {
  28.             openSpaces++;
  29.         }
  30.  
  31.         if(Y + 1 <= grid[0].length - 1 && grid[X][Y+1] == 0) {
  32.             openSpaces++;
  33.         }
  34.  
  35.         if(Y - 1 >= 0 && grid[X][Y-1] == 0) {
  36.             openSpaces++;
  37.         }
  38.  
  39.         return openSpaces > 0;
  40.     }
  41.  
  42.     private static void bfsForKnowingIsland(Queue<GridPair> q, Queue<GridPair> bfsq, int[][] grid, boolean[][] visited) {
  43.  
  44.         while (!bfsq.isEmpty()) {
  45.  
  46.             GridPair currPair = bfsq.poll();
  47.             int X = currPair.r;
  48.             int Y = currPair.c;
  49.  
  50.             if(isBoundary(X, Y, grid)) {
  51.                 q.offer(new GridPair(X, Y));
  52.             }
  53.  
  54.             int[] dirs = {-1, 0, 1, 0, -1};
  55.  
  56.             for(int i = 0; i < 4; i++) {
  57.  
  58.                 int newX = X + dirs[i];
  59.                 int newY = Y + dirs[i + 1];
  60.  
  61.                 if(newX <= grid.length - 1 && newX >= 0 && newY <= grid[0].length - 1 && newY >= 0 && !visited[newX][newY]) {
  62.  
  63.                     if(grid[newX][newY] == 1) {
  64.                         visited[newX][newY] = true;
  65.                         bfsq.offer(new GridPair(newX, newY));
  66.                     }
  67.  
  68.                 }
  69.             }
  70.  
  71.         }
  72.  
  73.     }
  74.     public static void main(String[] args) {
  75.  
  76.         Scanner scanner = new Scanner(System.in);
  77.  
  78.         int rows = scanner.nextInt();
  79.         int cols = scanner.nextInt();
  80.  
  81.         int[][] grid = new int[rows][cols];
  82.  
  83.         for(int i = 0; i < rows; i++) {
  84.             for(int j = 0; j < cols; j++) {
  85.                 grid[i][j] = scanner.nextInt();
  86.             }
  87.         }
  88.  
  89.         boolean[][] visited = new boolean[rows][cols];
  90.  
  91.         Queue<GridPair> q = new LinkedList<>();
  92.         Queue<GridPair> bfsq = new LinkedList<>();
  93.  
  94.         for(int i = 0; i < rows; i++) {
  95.  
  96.             boolean broke = false;
  97.  
  98.             for(int j = 0; j < cols; j++) {
  99.                 if(grid[i][j] == 1) {
  100.                     visited[i][j] = true;
  101.                     bfsq.offer(new GridPair(i, j));
  102.                     bfsForKnowingIsland(q, bfsq, grid, visited);
  103.                     broke = true;
  104.                     break;
  105.                 }
  106.             }
  107.  
  108.             if(broke) {
  109.                 break;
  110.             }
  111.  
  112.         }
  113.  
  114.         int ans = 0;
  115.  
  116.         while (!q.isEmpty()) {
  117.  
  118.             int currSize = q.size();
  119.  
  120.             for(int i = 0; i < currSize; i++) {
  121.  
  122.                 GridPair currPair = q.poll();
  123.                 int currX = currPair.r;
  124.                 int currY = currPair.c;
  125.  
  126.                 int[] dirs = {-1, 0, 1, 0, -1};
  127.  
  128.                 for(int j = 0; j < 4; j++) {
  129.  
  130.                     int newX = currX + dirs[j];
  131.                     int newY = currY + dirs[j + 1];
  132.  
  133.                     if(newX <= grid.length - 1 && newX >= 0 && newY <= grid[0].length - 1 && newY >= 0 && !visited[newX][newY]) {
  134.  
  135.                         if(grid[newX][newY] == 1) {
  136.                             System.out.println(ans);
  137.                             return;
  138.                         }
  139.  
  140.                         else {
  141.                             visited[newX][newY] = true;
  142.                             q.offer(new GridPair(newX, newY));
  143.                         }
  144.  
  145.                     }
  146.                 }
  147.  
  148.             }
  149.  
  150.             ans++;
  151.  
  152.         }
  153.  
  154.         System.out.println(ans);
  155.     }
  156. }
Success #stdin #stdout 0.19s 56356KB
comments (?)
stdin
copy 
8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0
0 0 0 0 1 0 1 1 0
0 0 1 1 1 0 0 0 0
0 1 1 0 1 0 0 0 0
0 1 0 0 1 0 0 0 0
0 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0
stdout
copy 
1
https://ideone.com/Mj3Q9f
language:
Java (HotSpot 12)
created:
1 day 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!