Last active
December 24, 2015 18:39
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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