Learn how to count the number of land cells in a grid that cannot reach the border by water. This step-by-step guide uses a multi-source BFS approach with clear, plain-English explanations and in-place code comments.<\/p>\n\n\n
\nYou are given an
m x n<\/code> binary gridgrid<\/code> where0<\/code> represents water and1<\/code> represents land.
A move consists of walking from one land cell to another adjacent (4-directional) land cell.
A land cell is called an enclave<\/strong> if it cannot reach the boundary of the grid by any number of moves.
Return the number of land cells in all enclaves<\/em>.<\/p>\n<\/blockquote>\n\n\n\nIntuition & Approach<\/h2>\n\n\n\n
\n
- Why BFS from the Border?<\/strong>
Any land (1<\/code>) that can reach<\/em> the boundary is not<\/strong> an enclave. If we start BFS from all<\/em> boundary land cells, we can mark every land cell that\u2019s connected to the edge.<\/li>\n\n\n\n- What\u2019s Left Over?<\/strong>
After that BFS, any land cell not<\/strong> visited must be unable to reach the border, that\u2019s exactly the count we want.<\/li>\n\n\n\n- High-Level Steps:<\/strong>\n
\n
- Create a
visited<\/code> grid, same size asgrid<\/code>, initialized to0<\/code> (unvisited).<\/li>\n\n\n\n- Enqueue every land cell on the four borders and mark them visited.<\/li>\n\n\n\n
- Run BFS: for each cell popped, enqueue its unvisited land neighbors and mark them.<\/li>\n\n\n\n
- Finally, scan the entire grid: every land cell that is still unvisited is an enclave, increment a counter.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
Code Implementation (with Comments)<\/h2>\n\n\n\n