mirror of https://github.com/evanferrao/dsa
111 lines
2.5 KiB
Java
111 lines
2.5 KiB
Java
import java.util.*;
|
|
import java.io.*;
|
|
|
|
class Main {
|
|
|
|
static class Node{
|
|
int row;
|
|
int col;
|
|
|
|
Node(int r, int c){
|
|
row = r;
|
|
col = c;
|
|
}
|
|
}
|
|
|
|
// DFS
|
|
public static void dfs(int r, int c, boolean vis[][], int grid[][]){
|
|
vis[r][c] = true;
|
|
|
|
int n = grid.length;
|
|
int m = grid[0].length;
|
|
|
|
// 8 directions
|
|
for(int dr = -1; dr <= 1; dr++){
|
|
for(int dc = -1; dc <= 1; dc++){
|
|
int nr = r + dr;
|
|
int nc = c + dc;
|
|
|
|
if(nr >= 0 && nr < n && nc >= 0 && nc < m &&
|
|
grid[nr][nc] == 1 && !vis[nr][nc]){
|
|
dfs(nr, nc, vis, grid);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
// BFS
|
|
public static void bfs(int r, int c, boolean vis[][], int grid[][]){
|
|
Queue<Node> q = new LinkedList<>();
|
|
|
|
q.add(new Node(r,c));
|
|
vis[r][c] = true;
|
|
|
|
int n = grid.length;
|
|
int m = grid[0].length;
|
|
|
|
while(!q.isEmpty()){
|
|
Node cur = q.poll();
|
|
|
|
for(int dr = -1; dr <= 1; dr++){
|
|
for(int dc = -1; dc <= 1; dc++){
|
|
int nr = cur.row + dr;
|
|
int nc = cur.col + dc;
|
|
|
|
if(nr >= 0 && nr < n && nc >= 0 && nc < m &&
|
|
grid[nr][nc] == 1 && !vis[nr][nc]){
|
|
vis[nr][nc] = true;
|
|
q.add(new Node(nr, nc));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
// ISLAND COUNT
|
|
public static int numIslands(int grid[][]) {
|
|
int n = grid.length;
|
|
int m = grid[0].length;
|
|
|
|
boolean vis[][] = new boolean[n][m];
|
|
int count = 0;
|
|
|
|
for(int i=0;i<n;i++){
|
|
for(int j=0;j<m;j++){
|
|
if(grid[i][j] == 1 && !vis[i][j]){
|
|
count++;
|
|
|
|
// choose one
|
|
dfs(i, j, vis, grid);
|
|
// bfs(i, j, vis, grid);
|
|
}
|
|
}
|
|
}
|
|
|
|
return count;
|
|
}
|
|
|
|
|
|
// DRIVER
|
|
public static void main(String[] args) {
|
|
|
|
int grid[][] = {
|
|
{1,1,0,0,0,0,0,1,1,0},
|
|
{1,1,0,0,0,0,0,1,1,0},
|
|
{0,0,0,1,0,0,0,0,0,0},
|
|
{0,0,0,1,1,1,0,0,1,0},
|
|
{0,0,0,0,0,0,0,0,1,0},
|
|
{1,1,0,0,0,0,1,0,0,0},
|
|
{1,1,0,0,0,0,1,1,0,0},
|
|
{0,0,0,0,1,0,0,0,0,0},
|
|
{0,1,1,0,0,0,0,0,1,1},
|
|
{0,1,1,0,0,0,0,0,1,1}
|
|
};
|
|
|
|
int ans = numIslands(grid);
|
|
System.out.printf("%d\n", ans);
|
|
}
|
|
}
|