<p>Given an <code>m x n</code> 2D binary grid <code>grid</code> which represents a map of <code>&#39;1&#39;</code>s (land) and <code>&#39;0&#39;</code>s (water), return <em>the number of islands</em>.</p>

<p>An <strong>island</strong> is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;]
]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;]
]
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>grid[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution {
public:
    using Matrix = std::vector<std::vector<char>>;
    using Coordinate = std::pair<int64_t, int64_t>;

    std::stack<Coordinate> m_Stack;
    std::vector<std::vector<bool>> m_Visited;

    std::array<Coordinate, 4> getNeighbours(int64_t x, int64_t y) {
        std::array<Coordinate, 4> neighbours;

        constexpr int16_t adjX[] = {-1, 1, 0, 0};
        constexpr int16_t adjY[] = {0, 0, -1, 1};

        for (size_t i = 0; i < 4; i++) {
            neighbours[i] = Coordinate{x + adjX[i], y + adjY[i]};
        }

        return neighbours;
    }

    bool isValid(const Matrix& m, int64_t x, int64_t y) {
        assert(!m.empty());

        const size_t rows = m.size();
        const size_t cols = m[0].size();

        return x >= 0 && y >= 0 && x < cols && y < rows;
    }

    bool visitShape(const Matrix& m, int64_t x, int64_t y) {
        if (m[y][x] != '1')
            return false;

        if (m_Visited[y][x])
            return false;

        m_Visited[y][x] = true;
        std::queue<Coordinate> bfsQueue;
        bfsQueue.emplace(x, y);

        while (!bfsQueue.empty()) {
            const auto [currX, currY] = bfsQueue.front();
            bfsQueue.pop();

            const auto neighbours = getNeighbours(currX, currY);
            for (const auto& [adjX, adjY] : neighbours) {
                if (isValid(m, adjX, adjY) && !m_Visited.at(adjY).at(adjX)) {
                    m_Visited[adjY][adjX] = true;
                    if (m[adjY][adjX] == '1') {
                        bfsQueue.emplace(adjX, adjY);
                    } else {
                        m_Stack.emplace(adjX, adjY);
                    }
                }
            }
        }

        return true;
    }

    size_t numIslands(Matrix& grid) {
        if (grid.empty())
            return 0;

        size_t islandCount = 0;
        m_Visited = std::vector<std::vector<bool>>(
            grid.size(), std::vector<bool>(grid[0].size(), false));

        if (!visitShape(grid, 0, 0)) {
            m_Stack.emplace(0, 0);
            m_Visited[0][0] = true;
        } else {
            islandCount++;
        }

        while (!m_Stack.empty()) {
            const auto& [currX, currY] = m_Stack.top();
            m_Stack.pop();

            const auto neighbours = getNeighbours(currX, currY);
            for (const auto& [adjX, adjY] : neighbours) {
                if (isValid(grid, adjX, adjY) && !m_Visited[adjY][adjX]) {
                    if (!visitShape(grid, adjX, adjY)) {
                        m_Stack.emplace(adjX, adjY);
                        m_Visited[adjY][adjX] = true;
                    } else {
                        islandCount++;
                    }
                }
            }
        }

        return islandCount;
    }
};
25588