• API
• FAQ
• Tools
• Archive
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;
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.

Top