<p>You are given an <code>m x n</code> binary matrix <code>grid</code>, where <code>0</code> represents a sea cell and <code>1</code> represents a land cell.</p>

<p>A <strong>move</strong> consists of walking from one land cell to another adjacent (<strong>4-directionally</strong>) land cell or walking off the boundary of the <code>grid</code>.</p>

<p>Return <em>the number of land cells in</em> <code>grid</code> <em>for which we cannot walk off the boundary of the grid in any number of <strong>moves</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/enclaves1.jpg" style="width: 333px; height: 333px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because its on the boundary.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/enclaves2.jpg" style="width: 333px; height: 333px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> All 1s are either on the boundary or can reach the boundary.
</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;= 500</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution {
public:
   void bfs(vector<vector<int>>& grid, vector<vector<int>>& visited, int i, int j, int &sum, int m, int n) { 
       int cnt = 1; // to count the number of land cells in this connected component
       queue<pair<int,int>> q;
       q.push({i, j});
       visited[i][j] = 1;
       bool flag = false; // to check if this component touches the boundary

       while (!q.empty()) {
           pair<int, int> a = q.front();
           q.pop();

           // Check if this cell is at the boundary
           if (a.first == 0 || a.second == 0 || a.first == m-1 || a.second == n-1) {
               flag = true;
           }

           // Explore the four directions (up, down, left, right)
           // Ensure indices are within bounds and cell is unvisited land
           if (a.first - 1 >= 0 && visited[a.first - 1][a.second] == 0 && grid[a.first - 1][a.second] == 1) {
               cnt++; 
               q.push({a.first - 1, a.second}); 
               visited[a.first - 1][a.second] = 1;
           }
           if (a.first + 1 < m && visited[a.first + 1][a.second] == 0 && grid[a.first + 1][a.second] == 1) {
               cnt++; 
               q.push({a.first + 1, a.second}); 
               visited[a.first + 1][a.second] = 1;
           }
           if (a.second - 1 >= 0 && visited[a.first][a.second - 1] == 0 && grid[a.first][a.second - 1] == 1) {
               cnt++; 
               q.push({a.first, a.second - 1}); 
               visited[a.first][a.second - 1] = 1;
           }
           if (a.second + 1 < n && visited[a.first][a.second + 1] == 0 && grid[a.first][a.second + 1] == 1) {
               cnt++; 
               q.push({a.first, a.second + 1}); 
               visited[a.first][a.second + 1] = 1;
           }
       }

       // If this component doesn't touch the boundary, add to sum
       if (!flag) {
           sum += cnt;
       }
   }

   int numEnclaves(vector<vector<int>>& grid) {
       int m = grid.size();
       int n = grid[0].size();
       vector<vector<int>> visited(m, vector<int>(n, 0));

       // Mark all water cells as visited
       for (int i = 0; i < m; i++) {
           for (int j = 0; j < n; j++) {
               if (grid[i][j] == 0) visited[i][j] = 1;
           }
       }

       int sum = 0;
       // Perform BFS on all unvisited land cells
       for (int i = 0; i < m; i++) {
           for (int j = 0; j < n; j++) {
               if (grid[i][j] == 1 && visited[i][j] == 0) {
                   bfs(grid, visited, i, j, sum, m, n);
               }
           }
       }
       return sum;
   }
};

54057