Given a binary matrix where 0 represents water and 1 represents land, count the number of islands in it. A island is formed by connected one’s.
For example, consider below image.
Above image highlights water in blue and land in grey in a 10 x 10 matrix. There are total five islands present in the above matrix. They are marked by numbers 1-5 in below image.
The idea is inspired from finding number of connected components in a graph problem and uses BFS.
The idea is to start BFS from each unprocessed node and increment the island count. Each BFS traversal will mark all cells which make one island as processed. So the problem reduces to finding number of BFS calls.
In each BFS traversal, we start by creating an empty queue. Then we enqueue starting cell and mark it as processed. Then we pop front node from the queue and process all 8 adjacent cells of current cell and enqueue each valid cell which is land. We repeat this process till queue is not empty.
We can find all the possible locations we can move to from the given location by using the array that stores the relative position of movement from any location. For example, if the current location is
(x, y), we can move to (x + row[k], y + col[k]) for 0 <= k <= 7 using below array.
int row[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int col[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
So, from position (x, y), we can move to:
(x – 1, y – 1)
(x – 1, y)
(x – 1, y + 1)
(x, y – 1)
(x, y + 1)
(x + 1, y – 1)
(x + 1, y)
(x + 1, y + 1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
#include <iostream> #include <queue> #include <cstring> using namespace std; // M x N matrix #define M 10 #define N 10 // Below arrays details all 8 possible movements from a cell // (top, right, bottom, left and 4 diagonal moves) int row[] = { -1, -1, -1, 0, 1, 0, 1, 1 }; int col[] = { -1, 1, 0, -1, -1, 1, 0, 1 }; // Function to check if it is safe to go to position (x, y) // from current position. The function returns false if (x, y) // is not valid matrix coordinates or (x, y) represents water or // position (x, y) is already processed bool isSafe(int mat[M][N], int x, int y, bool processed[M][N]) { return (x >= 0) && (x < M) && (y >= 0) && (y < N) && (mat[x][y] && !processed[x][y]); } void BFS(int mat[M][N], bool processed[M][N], int i, int j) { // create an empty queue and enqueue source node queue<pair<int, int>> q; q.push(make_pair(i, j)); // mark source node as processed processed[i][j] = true; // run till queue is not empty while (!q.empty()) { // pop front node from queue and process it int x = q.front().first; int y = q.front().second; q.pop(); // check for all 8 possible movements from current cell // and enqueue each valid movement for (int k = 0; k < 8; k++) { // skip if location is invalid or it is already // processed or consists of water if (isSafe(mat, x + row[k], y + col[k], processed)) { // mark it processed & push it into the queue processed[x + row[k]][y + col[k]] = 1; q.push(make_pair(x + row[k], y + col[k])); } } } } // main function int main() { int mat[M][N]= { { 1, 0, 1, 0, 0, 0, 1, 1, 1, 1 }, { 0, 0, 1, 0, 1, 0, 1, 0, 0, 0 }, { 1, 1, 1, 1, 0, 0, 1, 0, 0, 0 }, { 1, 0, 0, 1, 0, 1, 0, 0, 0, 0 }, { 1, 1, 1, 1, 0, 0, 0, 1, 1, 1 }, { 0, 1, 0, 1, 0, 0, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 1, 0, 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1, 0, 0, 1, 0, 0 }, { 1, 1, 1, 1, 0, 0, 0, 1, 1, 1 } }; // stores if cell is processed or not bool processed[M][N]; // mark all cells as unprocessed memset(processed, 0, sizeof(processed)); int island = 0; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // start BFS from each unprocessed node and // increment island count if (mat[i][j] && processed[i][j] == 0) { BFS(mat, processed, i, j); island++; } } } cout << "Number of islands are " << island << '\n'; return 0; } |
Output:
Number of islands are 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
import java.util.ArrayDeque; import java.util.Queue; class Pair { int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } } class CountIslands { // Below arrays details all 8 possible movements from a cell // (top, right, bottom, left and 4 diagonal moves) private static final int[] row = { -1, -1, -1, 0, 1, 0, 1, 1 }; private static final int[] col = { -1, 1, 0, -1, -1, 1, 0, 1 }; // Function to check if it is safe to go to position (x, y) // from current position. The function returns false if (x, y) // is not valid matrix cordinates or (x, y) represents water or // position (x, y) is already processed public static boolean isSafe(int[][] mat, int x, int y, boolean[][] processed) { return (x >= 0) && (x < processed.length) && (y >= 0) && (y < processed[0].length) && (mat[x][y] == 1 && !processed[x][y]); } public static void BFS(int[][] mat, boolean[][] processed, int i, int j) { // create an empty queue and enqueue source node Queue<Pair> q = new ArrayDeque<>(); q.add(new Pair(i, j)); // mark source node as processed processed[i][j] = true; // run till queue is not empty while (!q.isEmpty()) { // pop front node from queue and process it int x = q.peek().x; int y = q.peek().y; q.poll(); // check for all 8 possible movements from current cell // and enqueue each valid movement for (int k = 0; k < 8; k++) { // Skip if location is invalid or already processed // or has water if (isSafe(mat, x + row[k], y + col[k], processed)) { // skip if location is invalid or it is already // processed or consists of water processed[x + row[k]][y + col[k]] = true; q.add(new Pair(x + row[k], y + col[k])); } } } } public static void main(String[] args) { int[][] mat= { { 1, 0, 1, 0, 0, 0, 1, 1, 1, 1 }, { 0, 0, 1, 0, 1, 0, 1, 0, 0, 0 }, { 1, 1, 1, 1, 0, 0, 1, 0, 0, 0 }, { 1, 0, 0, 1, 0, 1, 0, 0, 0, 0 }, { 1, 1, 1, 1, 0, 0, 0, 1, 1, 1 }, { 0, 1, 0, 1, 0, 0, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 1, 0, 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1, 0, 0, 1, 0, 0 }, { 1, 1, 1, 1, 0, 0, 0, 1, 1, 1 } }; int M = mat.length; int N = mat[0].length; // stores if cell is processed or not boolean[][] processed = new boolean[M][N]; int island = 0; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // start BFS from each unprocessed node and // increment island count if (mat[i][j] == 1 && !processed[i][j]) { BFS(mat, processed, i, j); island++; } } } System.out.print("Number of islands are " + island); } } |
Output:
Number of islands are 5
Time complexity of above solution is O(MN).
Exercise: Solve above problem using DFS
Thanks for reading.
Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply