class Solution:
def numIslands(self, grid) -> int:
def dfs_islands(i, j, n, m):
if i < 0 or j < 0 or i == n or j == m or grid[i][j] != "1":
return
grid[i][j] = "-1"
dfs_islands(i+1, j, n, m)
dfs_islands(i-1, j, n, m)
dfs_islands(i, j+1, n, m)
dfs_islands(i, j-1, n, m)
n = len(grid)
m = len(grid[0])
res = 0
for i in range(n):
for j in range(m):
if grid[i][j] == "1":
res += 1
dfs_islands(i, j, n, m)
return res
class Solution {
public int numIslands(char[][] grid) {
int islands = 0;
int m = grid.length;
int n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
islands++;
dfs(grid, i, j);
}
}
}
return islands;
}
public void dfs(char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
dfs(grid, i+1, j);
dfs(grid, i-1, j);
dfs(grid, i, j+1);
dfs(grid, i, j-1);
}
}
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
n = len(grid)
m = len(grid[0])
distance = [[-1 , 0] , [1 , 0] , [0 , 1] , [0 , -1]]
def dfs(i , j):
grid[i][j] = '?'
for [x , y] in distance:
xx = i + x
yy = j + y
if 0 <= xx < n and m > yy >=0 and grid[xx][yy] == '1': dfs(xx , yy)
return
cnt = 0
for i in range(n):
for j in range(m):
if grid[i][j] == '1':
dfs(i , j)
cnt += 1
return cnt
var numIslands = function(grid) {
if (grid.length === 0) return 0;
let row = grid.length;
let col = grid[0].length;
let result = 0;
let dfs = (grid, r, c) => {
if (r < 0 || c < 0 || r >= row || c >= col || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
for (let r = 0; r < row; r++) {
for (let c = 0; c < col; c++) {
if (grid[r][c] == '1') {
result++;
dfs(grid, r, c);
}
}
}
return result;
};
public class Solution {
public int NumIslands(char[][] grid)
{
int m = grid.Length;
int n = grid[0].Length;
var visited = new int[m][];
for (int i = 0; i < m; i++)
{
visited[i] = new int[n];
}
int islandNumber = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == '1' && visited[i][j] == 0)
{
findIsland(i, j , grid, visited, ++islandNumber);
}
}
}
return islandNumber;
}
private void findIsland(int i, int j, char[][] grid, int[][] visited, int islandNumber)
{
if (i >= 0 && i < grid.Length && j >= 0 && j < grid[0].Length && visited[i][j] == 0)
{
visited[i][j] = islandNumber;
if (grid[i][j] == '1')
{
findIsland(i, j + 1, grid, visited, islandNumber);
findIsland(i, j - 1, grid, visited, islandNumber);
findIsland(i + 1, j, grid, visited, islandNumber);
findIsland(i - 1, j, grid, visited, islandNumber);
}
}
}
}
class Solution:
def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
ans = []
m = len(land)
n = len(land[0])
def dfs(row, column):
maxRow = row
maxColumn = column
land[row][column] = 0
for dx, dy in directions:
neighborRow = row + dx
neighborColumn = column + dy
if 0 <= neighborRow < m and 0 <= neighborColumn < n and land[neighborRow][neighborColumn] == 1:
neighbor = dfs(neighborRow, neighborColumn)
maxRow = max(maxRow, neighbor[0])
maxColumn = max(maxColumn, neighbor[1])
return [maxRow, maxColumn]
for i in range(m):
for j in range(n):
if land[i][j] == 1:
maxRow, maxColumn = dfs(i, j)
ans.append([i, j, maxRow, maxColumn])
return ans
void dfs(int r, int c, vector<vector<int>>& land, vector<vector<int>>& ret) {
int rows = land.size(), colums = land[0].size();
if(r < 0 || r >= rows || c < 0 || c >= colums || land[r][c] == 0) return;
land[r][c] = 0; // Mark as visited
auto& g = ret.back();
g[0] = min(r, g[0]); // Có thể ko cần vì duyệt từ nhỏ đến lớn
g[1] = min(c, g[1]); // Có thể ko cần vì duyệt từ nhỏ đến lớn
g[2] = max(r, g[2]);
g[3] = max(c, g[3]);
dfs(r-1, c, land, ret);
dfs(r+1, c, land, ret);
dfs(r, c+1, land, ret);
dfs(r, c-1, land, ret);
}
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
int rows = land.size(), colums = land[0].size();
vector<vector<int>> ret;
for(int r = 0; r < rows; ++r) {
for(int c = 0; c < colums; ++c) {
if (!land[r][c]) continue;
ret.push_back({r, c, r, c});
dfs(r, c, land, ret);
}
}
return ret;
}
class Solution {
public int[][] findFarmland(int[][] land) {
List<int[]> res = new ArrayList<>();
for (int col = 0; col < land[0].length; ++col) {
for (int row = 0; row < land.length; ++row) {
if (land[row][col] == 1) {
res.add(new int[4]);
res.get(res.size() - 1)[0] = (row);
res.get(res.size() - 1)[1] = (col);
dfs(land, row, col, res, res.size() - 1);
}
}
}
return res.toArray(new int[0][]);
}
public void dfs(int[][] land, int row, int col, List<int[]> res, int currIndex) {
if (row < 0 || col < 0 || row >= land.length || col >= land[0].length || land[row][col] == 0) return;
land[row][col] = 0;
if (res.get(currIndex)[2] <= row && res.get(currIndex)[3] <= col) {
res.get(currIndex)[2] = row;
res.get(currIndex)[3] = col;
}
dfs(land, row - 1, col, res, currIndex);
dfs(land, row, col - 1, res, currIndex);
dfs(land, row + 1, col, res, currIndex);
dfs(land, row, col + 1, res, currIndex);
}
}
class Solution:
def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
result = []
m, n = len(land), len(land[0])
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def dfs(u, v, m, n):
if land[u][v] == 0:
return [-1, -1]
land[u][v] = 0
botRight = [u, v]
for direction in directions:
dx, dy = direction
if u + dx >= 0 and u + dx < m and v + dy >= 0 and v + dy < n:
u1, v1 = dfs(u + dx, v + dy, m, n)
if botRight[0] < u1:
botRight[0] = u1
if botRight[1] < v1:
botRight[1] = v1
return botRight
for i in range(m):
for j in range(n):
if land[i][j] == 1:
botRight = dfs(i, j, m, n)
result.append([i, j, botRight[0], botRight[1]])
return result
private int[] findCoordinates(int[][] land, int row, int col) {
int[] coordinates = new int[4];
coordinates[0] = row;
coordinates[1] = col;
int numRows = land.length;
int numCols = land[0].length;
int currentRow = row;
int currentCol = col;
// Because the farmland is a rectangle
// thus we explore over cols and rows of land
while (currentRow < numRows && land[currentRow][col] == 1) {
currentRow++;
}
while (currentCol < numCols && land[row][currentCol] == 1) {
currentCol++;
}
coordinates[2] = currentRow - 1;
coordinates[3] = currentCol - 1;
// Mark current land = 0
for (int i = row; i < currentRow; i++) {
for (int j = col; j < currentCol; j++) {
land[i][j] = 0;
}
}
return coordinates;
}
/**
* Time: O(mn)
* Space: O(mn)
*/
public int[][] findFarmland(int[][] land) {
int numRows = land.length;
int numCols = land[0].length;
ArrayList<int[]> farmland = new ArrayList<>();
for (int row = 0; row < numRows; row++) {
for (int col = 0; col < numCols; col++) {
if (land[row][col] == 1) {
int[] coordinates = findCoordinates(land, row, col);
farmland.add(coordinates);
}
}
}
return farmland.toArray(new int[farmland.size()][]);
}var findFarmland = function(land) {
let row = land.length;
let col = land[0].length;
let result = [];
for (let i = 0; i < row; i++) {
for (let j = 0; j < col ;j++) {
if (land[i][j]) {
let isTopForest = i === 0 || !land[i - 1][j];
let isLeftForest = !land[i][j - 1];
// Check if we met the top left piece of the land
if (isTopForest && isLeftForest) {
let iEnd = i + 1;
let jEnd = j + 1;
// Measuring the borders
while (land[i][jEnd]) {jEnd++};
while (iEnd < row && land[iEnd][jEnd - 1]) {iEnd++};
result.push([i, j, iEnd - 1, jEnd - 1]);
j = jEnd;
}
}
}
}
return result;
};
class Solution {
public int[][] findFarmland(int[][] land) {
int rows= land.length;
int cols=land[0].length;
List<int[]> farmland = new ArrayList<>();
for(int i = 0 ; i<rows;i++){
for(int j =0;j<cols;j++){
if(land[i][j]==1){
farmland.add(dfs(land, i,j,rows,cols));
}
}
}
int[][] ans = farmland.toArray(new int[farmland.size()][4]);
return ans;
}
private int[] dfs(int[][] land, int row, int col, int rows, int cols){
int[] farm = new int[4];
farm[0]=row;
farm[1]=col;
while(row+1<rows && land[row+1][farm[1]]==1) {
row++;
}
while(col+1<cols && land[farm[0]][col+1]==1){
col++;
}
farm[2]=row;
farm[3]=col;
for(int i=farm[0];i<=row;i++){
for(int j=farm[1];j<=col;j++){
land[i][j]=-1;
}
}
return farm;
}
}
var findFarmland = function(land) {
const m = land.length, n = land[0].length, ans = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (land[i][j] === 0) {
continue;
}
if (i > 0 && Array.isArray(land[i-1][j])) {
land[i][j] = land[i-1][j];
} else if (j > 0 && Array.isArray(land[i][j-1])) {
land[i][j] = land[i][j-1];
} else {
land[i][j] = [i, j, 0, 0];
ans.push(land[i][j]);
}
const arr = land[i][j];;
arr[2] = Math.max(arr[2], i);
arr[3] = Math.max(arr[3], j);
}
}
return ans;
};
from queue import Queue
class Solution:
def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
row = len(land)
col = len(land[0])
queue = Queue()
result = []
for i in range(row):
for j in range(col):
if land[i][j]:
minPoint = (i, j)
maxPoint = (i, j)
queue.put((i, j))
land[i][j] = 0
while not queue.empty():
(curR, curC) = queue.get()
if curR < row - 1 and land[curR+1][curC]:
if maxPoint[0] < curR + 1 or maxPoint[1] < curC:
maxPoint = (curR+1, curC)
land[curR+1][curC] = 0
queue.put((curR+1, curC))
if curC < col - 1 and land[curR][curC+1]:
if maxPoint[0] < curR or maxPoint[1] < curC + 1:
maxPoint = (curR, curC+1)
land[curR][curC+1] = 0
queue.put((curR, curC+1))
result.append([minPoint[0], minPoint[1], maxPoint[0], maxPoint[1]])
return result
public class Solution
{
public int[][] FindFarmland(int[][] land)
{
int rows = land.Length;
int cols = land[0].Length;
HashSet<(int, int)> visited = new();
List<int[]> result = new();
int[][] dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (int row = 0; row < rows; row++)
{
for (int col = 0; col < cols; col++)
{
if (land[row][col] == 1 && !visited.Contains((row, col)))
{
int[] bounds = Dfs(land, visited, row, col, dirs);
result.Add(bounds);
}
}
}
return result.ToArray();
}
private int[] Dfs(int[][] land, HashSet<(int, int)> visited, int row, int col, int[][] dirs)
{
Stack<(int, int)> st = new();
st.Push((row, col));
visited.Add((row, col));
int minRow = row;
int minCol = col;
int maxRow = row;
int maxCol = col;
while (st.Count > 0)
{
var (r, c) = st.Pop();
for (int i = 0; i < dirs.Length; i++)
{
int dr = r + dirs[i][0];
int dc = c + dirs[i][1];
if (0 <= dr && dr < land.Length && 0 <= dc && dc < land[0].Length
&& land[dr][dc] == 1 && !visited.Contains((dr, dc)))
{
visited.Add((dr, dc));
st.Push((dr, dc));
minRow = Math.Min(minRow, dr);
minCol = Math.Min(minCol, dc);
maxRow = Math.Max(maxRow, dr);
maxCol = Math.Max(maxCol, dc);
}
}
}
return [minRow, minCol, maxRow, maxCol];
}
}
var findFarmland = function(land) {
let res = [];
let rows = land.length;
let cols = land[0].length;
var dfsx = function (r, c) {
if (r >= rows || land[r][c] == 0) return r - 1;
land[r][c] = 0;
return dfsx(r + 1, c);
}
var dfsy = function (r, c) {
if (c >= cols || land[r][c] == 0) return c - 1;
land[r][c] = 0;
return dfsy(r, c + 1);
}
var mark = function (r, c, x, y) {
for (let i = r + 1; i <= x; i++) {
for (let j = c + 1; j <= y; j++) {
land[i][j] = 0;
}
}
}
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
if (land[row][col] == 1) {
let x = dfsx(row + 1, col);
let y = dfsy(row, col + 1);
mark(row, col, x, y);
res.push([row, col, x, y]);
}
}
}
return res;
};
class Solution {
public:
void dfs(vector<vector<int>>& land, int r, int c, vector<vector<int>> &result)
{
if(r<0||c<0||r>=land.size()||c>=land[0].size()|| land[r][c] == 0) return;
land[r][c] = 0;
auto &vLast = result.back();
vLast[0] = min(r,vLast[0]); vLast[1] = min(c,vLast[1]);
vLast[2] = max(r,vLast[2]); vLast[3] = max(c,vLast[3]);
dfs(land,r-1,c, result);
dfs(land,r+1,c, result);
dfs(land,r,c-1, result);
dfs(land,r,c+1, result);
}
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
vector<vector<int>> result;
auto m = land.size();
auto n = land[0].size();
for(auto r=0;r<m;++r)
{
for(auto c=0;c<n;++c)
{
if(land[r][c] == 1)
{
result.push_back({r,c,r,c});
dfs(land,r,c, result);
}
}
}
return result;
}
};
class Solution {
public int[][] findFarmland(int[][] land) {
List<Integer[]> list = new ArrayList<>();
for(int i = 0; i < land.length; i++){
for(int j = 0; j < land[0].length; j++){
if(land[i][j] == 1){
Integer[] group = new Integer[]{i,j,i,j};
dfs(land, group, i, j);
list.add(group);
}
}
}
int[][] ans = new int[list.size()][4];
for(int i = 0; i < list.size(); i++){
ans[i][0] = list.get(i)[0];
ans[i][1] = list.get(i)[1];
ans[i][2] = list.get(i)[2];
ans[i][3] = list.get(i)[3];
}
return ans;
}
public void dfs(int[][] land, Integer[] group, int row, int col){
if(col < 0 || row < 0 || row >= land.length || col >= land[0].length || land[row][col] != 1)
return;
land[row][col] = 0;
if(group[2] == row){
group[3] = Math.max(col, group[3]);
}else if(group[2] < row){
group[2] = row;
group[3] = col;
}
group[2] = Math.max(row, group[2]);
dfs(land, group, row, col + 1);
dfs(land, group, row + 1, col);
dfs(land, group, row, col - 1);
dfs(land, group, row - 1, col);
}
}
class Solution {
List<int[]> listArr;
public int[][] findFarmland(int[][] land) {
int m = land.length;
int n = land[0].length;
listArr = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (land[i][j] == 1) {
dfs(i, j, i, j, land);
}
}
}
int[][] ans = new int[listArr.size()][4];
for (int i = 0; i < listArr.size(); i++) {
ans[i] = listArr.get(i);
}
return ans;
}
private void dfs(int originalRow, int originalCol, int row, int col, int[][] land) {
int m = land.length;
int n = land[0].length;
if (row >= m || col >= n || land[row][col] != 1) {
return;
}
boolean down = row < m - 1 && land[row + 1][col] == 1;
boolean right = col < n -1 && land[row][col + 1] == 1;
boolean blocked = (row == m - 1 || land[row + 1][col] == 0) && (col == n - 1 || land[row][col + 1] == 0);
land[row][col] = 2;
if (down) {
dfs(originalRow, originalCol, row + 1, col, land);
}
if (right) {
dfs(originalRow, originalCol, row, col + 1, land);
}
if (blocked) {
listArr.add(new int[] {originalRow, originalCol, row, col});
}
}
}
class Solution {
public:
vector<vector<int>> findFarmland(vector<vector<int>>& land) {
vector<vector<int>> res;
for (int i = 0; i < land.size(); ++i) {
for (int j = 0; j < land[0].size(); ++j) {
if (land[i][j]) {
res.emplace_back(initializer_list<int>{i, j, i, j});
dfs(i, j, land, res);
}
}
}
return res;
}
void dfs(int i, int j, vector<vector<int>>& land, vector<vector<int>>& res) {
land[i][j] = 0;
int n = res.size();
if (i < res[n - 1][0] || j < res[n - 1][1]) res[n - 1][0] = i, res[n - 1][1] = j;
if (i > res[n - 1][2] || j > res[n - 1][3]) res[n - 1][2] = i, res[n - 1][3] = j;
if (i > 0 && land[i - 1][j] == 1) dfs(i - 1, j, land, res);
if (i < land.size() - 1 && land[i + 1][j] == 1) dfs(i + 1, j, land, res);
if (j > 0 && land[i][j - 1] == 1) dfs(i, j - 1, land, res);
if (j < land[0].size() - 1 && land[i][j + 1] == 1) dfs(i, j + 1, land, res);
}
};
