SHARE
TWEET

Untitled

a guest Jun 19th, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class IslandMap implements Map {
  2.  
  3.     private boolean[][] map;
  4.  
  5.     public IslandMap(boolean[][] map) {
  6.         this.map = map;
  7.     }
  8.  
  9.     /* Returns a number of isolated "islands" (groups of "lands") on the map,
  10.      * where 'true' means land, 'false' means sea.
  11.      * Creates a copy of a map not to change the actual map.
  12.      *
  13.      * Time complexity: O(N),
  14.      * Space complexity: O(N),
  15.      * where N is a number of cells in a map
  16.      *
  17.      */
  18.  
  19.     public int countIslands() {
  20.         boolean[][] mapCopy = copyMap(map);
  21.         int counter = 0;
  22.         for (int i = 0; i < map.length; i++) {
  23.             for (int j = 0; j < map[i].length; j++) {
  24.                 if (mapCopy[i][j]) {
  25.                     counter++;
  26.                     markIslandAsVisited(mapCopy, i, j);
  27.                 }
  28.             }
  29.         }
  30.  
  31.         return counter;
  32.     }
  33.  
  34.     /*
  35.      * Marks a piece of land from the map as sea not to count the same island several times
  36.      * Recursively checks adjacent cells and marks them as water
  37.      *
  38.      * Time complexity: O(N),
  39.      * Space complexity: O(N)
  40.      * where N is a number of cells in a map
  41.      *
  42.      * @param map is a map marked with seas and lands
  43.      * @param i is a row where current cell is located
  44.      * @param j is a column where current cell is located
  45.      */
  46.  
  47.     private void markIslandAsVisited(boolean[][] map, int i, int j) {
  48.         if (!coordinateIsValid(i, j)) {
  49.             return;
  50.         }
  51.         if (!map[i][j]) {
  52.             return;
  53.         }
  54.  
  55.         map[i][j] = false;
  56.         markAdjacentCells(map, i, j);
  57.     }
  58.  
  59.     private void markAdjacentCells(boolean[][] map, int i, int j) {
  60.         markIslandAsVisited(map, i+1, j);
  61.         markIslandAsVisited(map, i-1, j);
  62.         markIslandAsVisited(map, i, j+1);
  63.         markIslandAsVisited(map, i, j-1);
  64.     }
  65.  
  66.     private static boolean[][] copyMap(boolean[][] map) {
  67.         boolean[][] copyMap = new boolean[map.length][map[0].length];
  68.         for (int i = 0; i < copyMap.length; i++) {
  69.             for (int j = 0; j < copyMap[i].length ; j++) {
  70.                 copyMap[i][j] = map[i][j];
  71.             }
  72.         }
  73.  
  74.         return copyMap;
  75.     }
  76.  
  77.     private boolean coordinateIsValid(int i, int j) {
  78.         return (i >= 0 && j >= 0 && i < map.length && j < map[i].length);
  79.     }
  80. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top