123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// DelRow and delCol for neighbors
vector<int> delRow = {-1, 0, 1, 0};
vector<int> delCol = {0, 1, 0, -1};
/* Helper Function to check if a
cell is within boundaries */
bool isValid(int &i, int &j,
int &n, int &m) {
// Return false if cell is invalid
if(i < 0 || i >= n) return false;
if(j < 0 || j >= m) return false;
// Return true if cell is valid
return true;
}
// Function to perform BFS traversal
void bfs(vector<vector<int>> &grid,
queue<pair<int,int>> &q,
vector<vector<bool>> &vis) {
// Getting the dimensions of image
int n = grid.size();
int m = grid[0].size();
// Until the queue is empty
while(!q.empty()) {
// Get the cell from queue
auto cell = q.front();
q.pop();
// Get its coordinates
int row = cell.first;
int col = cell.second;
// Traverse its 4 neighbors
for(int i=0; i < 4; i++) {
// Coordinates of new cell
int nRow = row + delRow[i];
int nCol = col + delCol[i];
/* check for valid, unvisited
and land cells */
if(isValid(nRow, nCol, n, m) &&
grid[nRow][nCol] == 1
&& vis[nRow][nCol] == false) {
/* Mark the new cell as visited
and add it to the queue */
vis[nRow][nCol] = true;
q.push({nRow, nCol});
}
}
}
}
public:
// Function to find number of enclaves
int numberOfEnclaves(vector<vector<int>> &grid) {
// Get the dimensions of grid
int n = grid.size();
int m = grid[0].size();
// Queue for BFS traversal
queue <pair<int,int>> q;
// Visited array
vector<vector<bool>> vis(n, vector<bool>(m, false));
/* Traverse the grid and add
the border land cells to queue */
for(int i=0; i < n; i++) {
for(int j=0; j < m; j++) {
/* If the land cell is at
border, add it to queue */
if((i == 0 || i == n-1 ||
j == 0 || j == m-1) &&
grid[i][j] == 1) {
vis[i][j] = true;
q.push({i, j});
}
}
}
/* Perform the bfs traversal
from border land cells */
bfs(grid, q, vis);
// Count to store number of enclaves
int count = 0;
// Traverse the grid
for(int i=0; i < n; i++) {
for(int j=0; j < m; j++){
/* If cell is a land cell and
unvisited, update the count */
if(grid[i][j] == 1 && !vis[i][j])
count++;
}
}
// Return count as answer
return count;
}
};
int main() {
vector<vector<int>> grid = {
{0, 0, 0, 1},
{1, 0, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0}
};
/* Creating an instance of
Solution class */
Solution sol;
// Function call to get number of enclaves
int ans = sol.numberOfEnclaves(grid);
cout << "The number of enclaves in given grid are: " << ans;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130
import java.util.*;
class Solution {
private int[] delRow = {-1, 0, 1, 0};
private int[] delCol = {0, 1, 0, -1};
/* Helper Function to check if a
cell is within boundaries */
private boolean isValid(int i, int j,
int n, int m) {
// Return false if cell is invalid
if(i < 0 || i >= n) return false;
if(j < 0 || j >= m) return false;
// Return true if cell is valid
return true;
}
// Function to perform BFS traversal
private void bfs(int[][] grid,
Queue<int[]> q,
boolean[][] vis) {
// Getting the dimensions of image
int n = grid.length;
int m = grid[0].length;
// Until the queue is empty
while(!q.isEmpty()) {
// Get the cell from queue
int[] cell = q.poll();
// Get its coordinates
int row = cell[0];
int col = cell[1];
// Traverse its 4 neighbors
for(int i=0; i < 4; i++) {
// Coordinates of new cell
int nRow = row + delRow[i];
int nCol = col + delCol[i];
/* check for valid, unvisited
and land cells */
if(isValid(nRow, nCol, n, m) &&
grid[nRow][nCol] == 1
&& vis[nRow][nCol] == false) {
/* Mark the new cell as visited
and add it to the queue */
vis[nRow][nCol] = true;
q.add(new int[]{nRow, nCol});
}
}
}
}
// Function to find number of enclaves
public int numberOfEnclaves(int[][] grid) {
// Get the dimensions of grid
int n = grid.length;
int m = grid[0].length;
// Queue for BFS traversal
Queue<int[]> q = new LinkedList<>();
// Visited array
boolean[][] vis = new boolean[n][m];
/* Traverse the grid and add
the border land cells to queue */
for(int i=0; i < n; i++) {
for(int j=0; j < m; j++) {
/* If the land cell is at
border, add it to queue */
if((i == 0 || i == n-1 ||
j == 0 || j == m-1) &&
grid[i][j] == 1) {
vis[i][j] = true;
q.add(new int[]{i, j});
}
}
}
/* Perform the bfs traversal
from border land cells */
bfs(grid, q, vis);
// Count to store number of enclaves
int count = 0;
// Traverse the grid
for(int i=0; i < n; i++) {
for(int j=0; j < m; j++){
/* If cell is a land cell and
unvisited, update the count */
if(grid[i][j] == 1 && !vis[i][j])
count++;
}
}
// Return count as answer
return count;
}
public static void main(String[] args) {
int[][] grid = {
{0, 0, 0, 1},
{1, 0, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0}
};
/* Creating an instance of
Solution class */
Solution sol = new Solution();
// Function call to get number of enclaves
int ans = sol.numberOfEnclaves(grid);
System.out.println("The number of enclaves in given grid are: " + ans);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116
from collections import deque
class Solution:
def __init__(self):
self.delRow = [-1, 0, 1, 0]
self.delCol = [0, 1, 0, -1]
# Helper Function to check if a
# cell is within boundaries
def isValid(self, i, j, n, m):
# Return false if cell is invalid
if i < 0 or i >= n:
return False
if j < 0 or j >= m:
return False
# Return true if cell is valid
return True
# Function to perform BFS traversal
def bfs(self, grid, q, vis):
# Getting the dimensions of image
n = len(grid)
m = len(grid[0])
# Until the queue is empty
while q:
# Get the cell from queue
cell = q.popleft()
# Get its coordinates
row, col = cell
# Traverse its 4 neighbors
for i in range(4):
# Coordinates of new cell
nRow = row + self.delRow[i]
nCol = col + self.delCol[i]
# check for valid, unvisited
# and land cells
if (self.isValid(nRow, nCol, n, m) and
grid[nRow][nCol] == 1 and
vis[nRow][nCol] == False):
# Mark the new cell as visited
# and add it to the queue
vis[nRow][nCol] = True
q.append((nRow, nCol))
# Function to find number of enclaves
def numberOfEnclaves(self, grid):
# Get the dimensions of grid
n = len(grid)
m = len(grid[0])
# Queue for BFS traversal
q = deque()
# Visited array
vis = [[False] * m for _ in range(n)]
# Traverse the grid and add
# the border land cells to queue
for i in range(n):
for j in range(m):
# If the land cell is at
# border, add it to queue
if ((i == 0 or i == n-1 or
j == 0 or j == m-1) and
grid[i][j] == 1):
vis[i][j] = True
q.append((i, j))
# Perform the bfs traversal
# from border land cells
self.bfs(grid, q, vis)
# Count to store number of enclaves
count = 0
# Traverse the grid
for i in range(n):
for j in range(m):
# If cell is a land cell and
# unvisited, update the count
if grid[i][j] == 1 and not vis[i][j]:
count += 1
# Return count as answer
return count
# Example usage
grid = [
[0, 0, 0, 1],
[1, 0, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 0]
]
# Creating an instance of
# Solution class
sol = Solution()
# Function call to get number of enclaves
ans = sol.numberOfEnclaves(grid)
print("The number of enclaves in given grid are:", ans)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128
class Solution {
constructor() {
this.delRow = [-1, 0, 1, 0];
this.delCol = [0, 1, 0, -1];
}
/* Helper Function to check if a
cell is within boundaries */
isValid(i, j, n, m) {
// Return false if cell is invalid
if (i < 0 || i >= n) return false;
if (j < 0 || j >= m) return false;
// Return true if cell is valid
return true;
}
// Function to perform BFS traversal
bfs(grid, q, vis) {
// Getting the dimensions of image
let n = grid.length;
let m = grid[0].length;
// Until the queue is empty
while (q.length > 0) {
// Get the cell from queue
let cell = q.shift();
// Get its coordinates
let row = cell[0];
let col = cell[1];
// Traverse its 4 neighbors
for (let i = 0; i < 4; i++) {
// Coordinates of new cell
let nRow = row + this.delRow[i];
let nCol = col + this.delCol[i];
/* check for valid, unvisited
and land cells */
if (this.isValid(nRow, nCol, n, m) &&
grid[nRow][nCol] === 1 &&
vis[nRow][nCol] === false) {
/* Mark the new cell as visited
and add it to the queue */
vis[nRow][nCol] = true;
q.push([nRow, nCol]);
}
}
}
}
// Function to find number of enclaves
numberOfEnclaves(grid) {
// Get the dimensions of grid
let n = grid.length;
let m = grid[0].length;
// Queue for BFS traversal
let q = [];
// Visited array
let vis = Array.from(
{ length: n },
() => Array(m).fill(false));
/* Traverse the grid and add
the border land cells to queue */
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
/* If the land cell is at
border, add it to queue */
if ((i === 0 || i === n-1 ||
j === 0 || j === m-1) &&
grid[i][j] === 1) {
vis[i][j] = true;
q.push([i, j]);
}
}
}
/* Perform the bfs traversal
from border land cells */
this.bfs(grid, q, vis);
// Count to store number of enclaves
let count = 0;
// Traverse the grid
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
/* If cell is a land cell and
unvisited, update the count */
if (grid[i][j] === 1 && !vis[i][j])
count++;
}
}
// Return count as answer
return count;
}
}
// Example usage
let grid = [
[0, 0, 0, 1],
[1, 0, 1, 0],
[0, 0, 1, 0],
[0, 0, 0, 0]
];
// Creating an instance of
// Solution class
let sol = new Solution();
// Function call to get number of enclaves
let ans = sol.numberOfEnclaves(grid);
console.log("The number of enclaves in given grid are:", ans);
