_1254.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.LinkedList;
importjava.util.Queue;

publicclass_1254 {
publicstaticclassSolution1 {
/*
 * BFS each cell in the grid with a visited matrix to avoid infinite loop.
 */
publicintclosedIsland(int[][] grid) {
intm = grid.length;
intn = grid[0].length;
boolean[][] visited = newboolean[m][n];
intcount = 0;
for (inti = 0; i < m; i++) {
for (intj = 0; j < n; j++) {
if (grid[i][j] == 0 && !visited[i][j] && bfs(i, j, m, n, grid, visited)) {
count++;
 }
 }
 }
returncount;
 }

privatebooleanbfs(intx, inty, intm, intn, int[][] grid, boolean[][] visited) {
int[] dirs = newint[] {0, 1, 0, -1, 0};
Queue<int[]> q = newLinkedList<>();
q.offer(newint[] {x, y});
booleanisClosed = true;
while (!q.isEmpty()) {
intsize = q.size();
for (inti = 0; i < size; i++) {
int[] curr = q.poll();
for (intj = 0; j < dirs.length - 1; j++) {
intnewx = dirs[j] + curr[0];
intnewy = dirs[j + 1] + curr[1];
if (newx < 0 || newx >= m || newy < 0 || newy >= n) {
// this means that (x,y) is a boundary cell
isClosed = false;
 } elseif (!visited[newx][newy] && grid[newx][newy] == 0) {
visited[newx][newy] = true;
q.offer(newint[] {newx, newy});
 }
 }
 }
 }
returnisClosed;
 }
 }
}