Skip to content

Instantly share code, notes, and snippets.

@agstudy
Last active December 24, 2015 18:39
Show Gist options
  • Save agstudy/6845022 to your computer and use it in GitHub Desktop.
Save agstudy/6845022 to your computer and use it in GitHub Desktop.
DFS to get the number of linked ones (islands) in a matrix of 1 and 0
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.awt.Point;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Maze
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int[][] vv = new int[][]{
{1,1,1,0,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,1,1,0,1,1}};
Maze maze = new Maze(vv);
System.out.println(maze.toString());
System.out.println("Islands number is " + maze.islandsNumber());
}
public Maze(int[][] values ){
this.values = values;
}
void setValues(int[][] values){ this.values = values; }
private int[][] values;
private boolean[][] visited;
private int nCol;
private int nRow;
private Point[] getNeighbors(Integer i, Integer j){
Point left = (i-1<0)?null:new Point(i-1,j);
Point right = (i+1>nRow-1)?null:new Point(i+1,j);
Point top = (j-1<0)?null:new Point(i,j-1);
Point bottom = (j+1>nCol-1)?null:new Point(i,j+1);
return new Point[]{left,right,top,bottom};
}
public int islandsNumber(){
int nislands = 0;
// init visited maze
nRow = values.length;
visited = new boolean[values.length][];
for (int i = 0;i<values.length;i++){
boolean[] row = new boolean[values[i].length];
if(nCol == 0) nCol = values[i].length;
for (int j = 0;j<values[i].length;j++)
row[j] = values[i][j]==1?false:true;
visited[i] = row;
}
// System.out.println(printArray(visited));
for(int i =0 ;i < nRow;i++)
for(int j=0 ;j < nCol ;j++){
if (!visited[i][j]){
nislands++;
explore(i,j);
}
}
// System.out.println(printArray(visited));
return nislands;
}
private void explore(int i , int j){
visited[i][j] = true;
Point[] neighobrs = getNeighbors(i,j);
for (int k =0;k<4;k++)
if(neighobrs[k] != null &&
!visited[neighobrs[k].x][neighobrs[k].y])
explore(neighobrs[k].x,neighobrs[k].y);
}
public String toString(){
return printArray(values);
}
private String printArray(int[][] values){
return Arrays.deepToString(values).
replaceAll("\\],", "]\n");
}
private String printArray(boolean[][] values){
return Arrays.deepToString(values).
replaceAll("\\],", "]\n");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment