Given a rectangular binary matrix representing a geographical map where character '1' indicates landmass and '0' represents water, the computational task is to enumerate distinct islands. An island forms when land cells connect horizontally or vertically; diagonal adjacency does not constitute valid connectivity. The grid periphery is assumed to be entirely surrounded by water.

Algorithmic Strategy

This scenario reduces to identifying connected components within an undirected grid graph, where each land cell functions as a vertex with potential edges to its four orthogonal neighbors. The algorithmic solution requires a complete scan of the matrix to locate unvisited land. Upon discovering land, graph traversal floods the entire connected region by marking visited cells as water, ensuring each geographical feature contributes exactly one to the aggregate count. Both Depth-First Search (DFS) and Breadth-First Search (BFS) provide valid traversal mechanisms.

Depth-First Search Implementation

The recursive approach initiates exploration from any discovered land coordinate, systematically investigating cardinal directions while immediately converting visited terrain to water. This containment strategy prevents redundant counting and naturally handles irregular island shapes through stack-based recursion.

class IslandCounter {
public:
    int countIslands(vector<vector<char>>& map) {
        if (map.empty() || map[0].empty()) return 0;
        
        int rows = map.size();
        int cols = map[0].size();
        int islands = 0;
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (map[r][c] == '1') {
                    explore(map, r, c, rows, cols);
                    ++islands;
                }
            }
        }
        return islands;
    }

private:
    void explore(vector<vector<char>>& map, int r, int c, int rows, int cols) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || map[r][c] == '0') 
            return;
            
        map[r][c] = '0';
        const vector<pair<int, int>> offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (auto [dr, dc] : offsets) {
            explore(map, r + dr, c + dc, rows, cols);
        }
    }
};

Breadth-First Search Implementation

For environments where recusrion depth might risk stack overflow on extensive landmasses, an iterative BFS approach employs a queue to manage frontier cells. Each dequeued coordinate triggers examination of adjacent positions, with newly discovered land immediately marked as visited and enqueued for subsequent processing.

class IslandCounter {
public:
    int countIslands(vector<vector<char>>& map) {
        if (map.empty() || map[0].empty()) return 0;
        
        int rows = map.size(), cols = map[0].size(), islands = 0;
        const vector<pair<int, int>> offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (map[r][c] == '1') {
                    floodFill(map, r, c, rows, cols, offsets);
                    ++islands;
                }
            }
        }
        return islands;
    }

private:
    void floodFill(vector<vector<char>>& map, int sr, int sc, int rows, int cols, 
                   const vector<pair<int, int>>& dirs) {
        queue<pair<int, int>> frontier;
        frontier.push({sr, sc});
        map[sr][sc] = '0';
        
        while (!frontier.empty()) {
            auto [r, c] = frontier.front();
            frontier.pop();
            
            for (auto [dr, dc] : dirs) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && map[nr][nc] == '1') {
                    map[nr][nc] = '0';
                    frontier.push({nr, nc});
                }
            }
        }
    }
};

Complexity Analysis

Both algorithms exhibit O(M × N) time complexity, where M and N denote matrix dimensions, since each cell undergoes constant-time processing exactly once. Space complexity reaches O(M × N) in the worst-case scenario where the entire matrix consists of a single island, requiring storage for the recursion stack (DFS) or queue (BFS).