Massive Algorithms: Leetcode 200: Find the number of islands

Find the number of islands | GeeksforGeeks
Given a boolean 2D matrix, find the number of islands.
This is an variation of the standard problem: “Counting number of connected components in a undirected graph”.
Time complexity: O(ROW x COL)
A connected component of an undirected graph is a subgraph in which every two vertices are connected to each other by a path(s), and which is connected to no other vertices outside the subgraph.
The problem can be easily solved by applying DFS() on each component. In each DFS() call, a component or a sub-graph is visited. We will call DFS on the next un-visited component. The number of calls to DFS() gives the number of connected components.

                        {1, 1, 0, 0, 0},
                        {0, 1, 0, 0, 1},
                        {1, 0, 0, 1, 1},
                        {0, 0, 0, 0, 0},
                        {1, 0, 1, 0, 1}

X. DFS
http://blog.csdn.net/xudli/article/details/45912547

void DFS(int M[][COL], int row, int col, bool visited[][COL])

{

    // These arrays are used to get row and column numbers of 8 neighbors 

    // of a given cell

    static int rowNbr[] = {-1, -1, -1,  0, 0,  1, 1, 1};

    static int colNbr[] = {-1,  0,  1, -1, 1, -1, 0, 1};

    // Mark this cell as visited

    visited[row][col] = true;

    // Recur for all connected neighbours

    for (int k = 0; k < 8; ++k)

        if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited) )

            DFS(M, row + rowNbr[k], col + colNbr[k], visited);

}

// The main function that returns count of islands in a given boolean

// 2D matrix

int countIslands(int M[][COL])

{

    // Make a bool array to mark visited cells.

    // Initially all cells are unvisited

    bool visited[ROW][COL];

    memset(visited, 0, sizeof(visited));

    // Initialize count as 0 and travese through the all cells of

    // given matrix

    int count = 0;

    for (int i = 0; i < ROW; ++i)

        for (int j = 0; j < COL; ++j)

            if (M[i][j] && !visited[i][j]) // If a cell with value 1 is not

            {                              // visited yet, then new island found

                DFS(M, i, j, visited);     // Visit all cells in this island.

                ++count;                   // and increment island count

}

    return count;

}

http://www.huhaoyu.com/leetcode-number-of-islands/

只需要对每一个陆地区域做一次dfs，每次dfs中将已经遍历的陆地网格“1”变为水域网格“2”（防止再次遍历导致重复）。对每次dfs计数，总共dfs的次数即为岛屿总数。应注意，grid为空的特殊情况应该排除。

http://www.programcreek.com/2014/04/leetcode-number-of-islands-java/
http://blog.csdn.net/ljiabin/article/details/44975717
https://discuss.leetcode.com/topic/13248/very-concise-java-ac-solution
Don't use extra visited space:
If we need restore grid, we just need map 2 to 1.

public int numIslands(char[][] grid) {
    if (grid==null || grid.length==0 || grid[0].length==0) return 0;
    int count = 0;
 
    for (int i=0; i<grid.length; i++) {
        for (int j=0; j<grid[0].length; j++) {
            if(grid[i][j] == '1'){
                count++;
                merge(grid, i, j);
            }
        }
    }
    return count;
}
 public void merge(char[][] grid, int i, int j){
    //validity checking
    if(i<0 || j<0 || i>grid.length-1 || j>grid[0].length-1)
        return;
 
    //if current cell is water or visited
    if(grid[i][j] != '1') return;
 
    //set visited cell to '2'
    grid[i][j] = '2';
 
    //merge all adjacent land
    merge(grid, i-1, j);
    merge(grid, i+1, j);
    merge(grid, i, j-1);
    merge(grid, i, j+1);
}

http://www.fgdsb.com/2015/02/09/number-of-islands/

X. BFS:
http://blog.hyoung.me/cn/2017/03/breadth-first-search/

这道题虽然简单，但包含了两个使用 BFS 时的关键技巧。第一，对于图（Graph）或矩阵（Board）而言，在使用 BFS 时往往就需要记录访问信息以避免重复访问。第二，对于矩阵而言，使用偏移变量（line 30~31）来表示搜索的方向往往会使得逻辑表达更加清楚，实现起来也更加简洁。

如前面所说，我们也同样可以使用 DFS 来解决。但栈中递归函数最多可能积累

O (N M)

次，即整个矩阵的大小，当

N

或

M

较大时，就有可能会爆栈。

http://www.cnblogs.com/tonyluis/p/4558750.html
-- Change origin data: 1 to 0.

public int numIslands(char[][] grid) {

    int res = 0;

    for (int i = 0; i < grid.length; i++)

        for (int j = 0; j < grid[0].length; j++)

            if (grid[i][j] == '1') {

                grid[i][j] = '0';

                bfs(grid, i * grid[0].length + j);

                res++;

}

    return res;

}

public static void bfs(char[][] grid, int num) {

    Queue<Integer> queue = new LinkedList<Integer>();

    queue.add(num);

    while (!queue.isEmpty()) {

        num = queue.poll();

        int row = num / grid[0].length;

        int col = num - row * grid[0].length;

        if (row - 1 >= 0 && grid[row - 1][col] == '1') {

            grid[row - 1][col] = '0';

            queue.add(num - grid[0].length);

}

        if (row + 1 <= grid.length - 1 && grid[row + 1][col] == '1') {

            grid[row + 1][col] = '0';

            queue.add(num + grid[0].length);

}

        if (col - 1 >= 0 && grid[row][col - 1] == '1') {

            grid[row][col - 1] = '0';

            queue.add(num - 1);

}

        if (col + 1 <= grid[0].length - 1 && grid[row][col + 1] == '1') {

            grid[row][col + 1] = '0';

            queue.add(num + 1);

}

}

}

http://blog.csdn.net/derrantcm/article/details/47970795
Don't change origin data. - Use extra visited array.
public int numIslands(char[][] grid) { // 参数校验 if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } // 元素默认值是false boolean[][] visited = new boolean[grid.length][grid[0].length]; int result = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { // 如果此位置没有被访问过，并且此位置是岛，就里德广度优先遍历 if (!visited[i][j] && grid[i][j] == '1') { result++; bfs(grid, visited, i, j); } } } return result; } private void bfs(char[][] grid, boolean[][] visited, int row, int col) { if (row >= 0 && row < grid.length // 行合法 && col >= 0 && col < grid[0].length // 列合法 && !visited[row][col] // 没有访问过 && grid[row][col] == '1') { // 是岛上陆地 // 标记此位置已经访问过了 visited[row][col] = true; // 上 bfs(grid, visited, row - 1, col); // 右 bfs(grid, visited, row, col + 1); // 下 bfs(grid, visited, row + 1, col); // 左 bfs(grid, visited, row, col - 1); } }
http://www.ideserve.co.in/learn/number-of-clusters-of-1s

X. Union Find
http://likesky3.iteye.com/blog/2240170
这里阐述下union-find思路，思路很直接，我们需要把相连在一起的1union起来，最后数下union了多少个集合1。输入时一个m*n矩阵，union-find相应地需要一个二维数组保存信息，采用按秩求并方法，初始时每个1元素的秩为-1,0元素不参与union，记为0。扫描数组，对于(i,j)元素，查看其是否需要同右边和下边相邻元素合并，其上边和左边不需要，因为按这种扫描顺序已经查看过。一个相邻的1集合合并完，只有根节点的秩为负数，而其余节点均指向相应根节点的下标为正数，因此扫描完整个集合，通过检查秩数组中负数的个数即可知道grid中的岛屿数。特别注意，在union时若两个元素根相同说明已经被union过，不能再执行union逻辑否则会导致该集合的根消失而Wrong Answer。

--第二版union find，一维数组存储，更清晰，使用count计数岛屿数，初始时每个1所在位置为一个岛屿，伴随union过程，相连的1代表的岛屿进行合并，每一次成功合并，岛屿数减一。实现如Method 4所示。当然此题用BFS或者DFS代码比较简洁, DFS的隐患是可能堆栈溢出。

public int numIslands1(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0)
return 0;
initUnionFind(grid);
int rows = grid.length;
int cols = grid[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
for (int k = 0; k < 4; k++) {
int iNeigh = i + deltaY[k];
int jNeigh = j + deltaX[k];
if (iNeigh >= 0 && iNeigh < rows && jNeigh >= 0 && jNeigh < cols && grid[iNeigh][jNeigh] == '1') {
union(i * cols + j, iNeigh * cols + jNeigh);
}
}
}
}
}
return count;
}
int[] s;
int[] rank;
int count = 0;
int[] deltaX = {0, 0, 1, -1};
int[] deltaY = {1, -1, 0, 0};
private void union(int p, int q) {
int pRoot = find(p), qRoot = find(q);
if (pRoot == qRoot) return;
if (s[pRoot] > s[qRoot]) {
s[pRoot] = qRoot;
} else {
if (s[pRoot] == s[qRoot])
s[pRoot]--;
s[qRoot] = pRoot;
}
count--;
}
private int find1(int p) {
if (s[p] == p)
return p;
else
return s[p] = find(s[p]);
}
private void union1(int p, int q) {
int pRoot = find(p), qRoot = find(q);
if (pRoot == qRoot) return;
if (rank[pRoot] < rank[qRoot]) {
s[pRoot] = qRoot;
} else {
if (rank[pRoot] == rank[qRoot])
rank[pRoot]++;
s[qRoot] = s[pRoot];
}
count--;
}

https://discuss.leetcode.com/topic/33947/java-union-find-solution

You only need to do it for two directions, which are "right" and "down", because all "left" and "up" has already been seen if exists connection (undirected for Union Find).

https://discuss.leetcode.com/topic/39980/1d-union-find-java-solution-easily-generalized-to-other-problems

   int[][] distance = {{1,0},{-1,0},{0,1},{0,-1}};
    public int numIslands(char[][] grid) {  
        if (grid == null || grid.length == 0 || grid[0].length == 0)  {
            return 0;  
        }
        UnionFind uf = new UnionFind(grid);  
        int rows = grid.length;  
        int cols = grid[0].length;  
        for (int i = 0; i < rows; i++) {  
            for (int j = 0; j < cols; j++) {  
                if (grid[i][j] == '1') {  
                    for (int[] d : distance) {
                        int x = i + d[0];
                        int y = j + d[1];
                        if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == '1') {  
                            int id1 = i*cols+j;
                            int id2 = x*cols+y;
                            uf.union(id1, id2);  
                        }  
                    }  
                }  
            }  
        }  
        return uf.count;  
    }

Union Find:

    class UnionFind {
        int[] father;  
        int m, n;
        int count = 0;
        UnionFind(char[][] grid) {  
            m = grid.length;  
            n = grid[0].length;  
            father = new int[m*n];  
            for (int i = 0; i < m; i++) {  
                for (int j = 0; j < n; j++) {  
                    if (grid[i][j] == '1') {
                        int id = i * n + j;
                        father[id] = id;
                        count++;
                    }
                }  
            }  
        }
        public void union(int node1, int node2) {  
            int find1 = find(node1);
            int find2 = find(node2);
            if(find1 != find2) {
                father[find1] = find2;
                count--;
            }
        }
        public int find (int node) {  
            if (father[node] == node) {  
                return node;
            }
            father[node] = find(father[node]);  
            return father[node];
        }
    }

https://leetcode.com/discuss/31768/ac-java-solution-using-union-find-with-explanations
Basic idea is to iterate through every node's neighbours and marked them if they aren't connected. Finally, if it was the root node then increase the total number of islands.
private int[] sz; private int[] id; private int N, M; public int find(int p) { while (id[p] != p) p = id[p]; return p; } public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; if (sz[rootP] < sz[rootQ]) {sz[rootQ] += sz[rootP]; id[rootP] = id[rootQ];} else {sz[rootP] += sz[rootQ]; id[rootQ] = id[rootP];} } private boolean inside(int x, int y) { return (x >= 0 && y >= 0 && x < N && y < M); } public int numIslands(char[][] grid) { if (grid == null || grid.length ==0) return 0; N = grid.length; M = grid[0].length; sz = new int[N*M]; id = new int[N*M]; for (int i = 0; i < N*M; i++) { id[i] = i; sz[i] = 1; } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) if (grid[i][j] != '0') { int tmp = i*M + j; if (inside(i-1, j) && grid[i-1][j] != '0') union(tmp, tmp - M); if (inside(i, j-1) && grid[i][j-1] != '0') union(tmp, tmp - 1); if (inside(i+1, j) && grid[i+1][j] != '0') union(tmp, tmp + M); if (inside(i, j+1) && grid[i][j+1] != '0') union(tmp, tmp + 1); } } int islands = 0, i = 0; while (i < N*M) { if (i == id[i] && grid[i/M][i%M] != '0') islands++; i++; } return islands; }
http://www.tangjikai.com/algorithms/leetcode-200-number-of-islands

class UnionFind(object):
def __init__(self, m, n):
self.father = dict()
self.count = m * n
for x in range(m):
for y in range(n):
Id = x * n + y
self.father[Id] = Id
def compressed_find(self, x):
parent = self.father.get(x)
while parent != self.father.get(parent):
parent = self.father.get(parent)
temp = -1
fa = self.father.get(x)
while fa != self.father.get(fa):
temp = self.father.get(fa)
self.father[fa] = parent
fa = temp
return parent
def union(self, x, y):
fa_x = self.compressed_find(x)
fa_y = self.compressed_find(y)
if fa_x != fa_y:
self.father[fa_x] = fa_y
self.count -=1
class Solution(object):
def convertToId(self, x, y, n):
return x * n + y
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if grid == None or len(grid) == 0:
return 0
m = len(grid)
n = len(grid[0])
uf = UnionFind(m, n)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
if i < m - 1 and grid[i+1][j] == '1':
uf.union(self.convertToId(i, j, n), self.convertToId(i+1, j, n))
if j < n - 1 and grid[i][j+1] == '1':
uf.union(self.convertToId(i, j, n), self.convertToId(i, j+1, n))
else:
uf.count -= 1
return uf.count

https://gist.github.com/pdu/6e950a13964701507252
private int[] sz;
private int[] id;
private int N, M;

public int find(int p) {
while (id[p] != p)
p = id[p];
return p;
}

public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;

if (sz[rootP] < sz[rootQ]) {sz[rootQ] += sz[rootP]; id[rootP] = id[rootQ];}
else {sz[rootP] += sz[rootQ]; id[rootQ] = id[rootP];}
}

private boolean inside(int x, int y) {
return (x >= 0 && y >= 0 && x < N && y < M);
}

public int numIslands(char[][] grid) {
if (grid == null || grid.length ==0) return 0;
N = grid.length;
M = grid[0].length;
sz = new int[N*M];
id = new int[N*M];
for (int i = 0; i < N*M; i++) {
id[i] = i;
sz[i] = 1;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
if (grid[i][j] != '0') {
int tmp = i*M + j;
if (inside(i-1, j) && grid[i-1][j] != '0') union(tmp, tmp - M);
if (inside(i, j-1) && grid[i][j-1] != '0') union(tmp, tmp - 1);
if (inside(i+1, j) && grid[i+1][j] != '0') union(tmp, tmp + M);
if (inside(i, j+1) && grid[i][j+1] != '0') union(tmp, tmp + 1);
}
}
int islands = 0, i = 0;
while (i < N*M) {
if (i == id[i] && grid[i/M][i%M] != '0') islands++;
i++;
}
return islands;
}

http://betterpoetrythancode.blogspot.com/2015/01/number-of-countries.html
https://leetcode.com/discuss/31768/ac-java-solution-using-union-find-with-explanations
public class Block{
int x;
int y;
public Block(int x,int y)
{
this.x=x;
this.y=y;
}
}
public int solution(int[][] board)
{
int TAG=Integer.MIN_VALUE;
int counter=0;
for(int i=0;i<board.length;i++)
{
for(int j=0;j<board[0].length;j++)
{
if(board[i][j]!=TAG)
{
bfs(board,i,j);
counter+=1;
}
}
}
return counter;
}
public void bfs(int[][] board,int startX,int startY)
{
int TAG1=Integer.MIN_VALUE;
int TAG2=board[startX][startY];
int m=board.length;
int n=board[0].length;
Queue<Block> queue=new LinkedList<Block>();
queue.offer(new Block(startX,startY));
while(queue.isEmpty()==false)
{
int queueSize=queue.size();
for(int i=0;i<queue.size();i++)
{
Block cur=queue.poll();
board[cur.x][cur.y]=TAG1;
if(cur.x+1<m&&board[cur.x+1][cur.y]==TAG2)
queue.offer(new Block(cur.x+1,cur.y));
if(cur.y+1<n&&board[cur.x][cur.y+1]==TAG2)
queue.offer(new Block(cur.x,cur.y+1));
if(cur.x-1>=0&&board[cur.x-1][cur.y]==TAG2)
queue.offer(new Block(cur.x-1,cur.y));
if(cur.y-1>=0&&board[cur.x][cur.y-1]==TAG2)
queue.offer(new Block(cur.x,cur.y-1));
}
}
}
Pond Sizes

You have an integer matrix representing a plot of land, where the value at that location

represents the height above sea level. A value of zero indicates water. A pond is a region of water

connected vertically, horizontally, or diagonally. The size of the pond is the total number of

connected water cells. Write a method to compute the sizes of all ponds in the matrix

Arraylist<Integer> computePondSizes(int[][] land) {
Arraylist<Integer> pondSizes = new Arraylist<Integer>();
for (int r = 0; r < land.length; r++) {
for (int c = 0; c < land[r].length; c++) {
if (land[r][c] == 0) {//Optional. Would return anyway.
int size = computeSize(land, r, c);
pondSizes.add(size);
}
}
}
return pondSizes;
}

int computeSize(int[][] land, int row, int col) {
/* If out of bounds or already visited. */
if (row < 0 || col< 0 || row >= land.length || col >= land[row].length || land[row][col) != 0) {
//visited or not water
return 0;
}
int size = 1;
land[row][col] = -1; // Mark visited
for (int dr = -1; dr <= 1; dr++) {
for (int de = -1; de <= 1; de++) {
size += computeSize(land, row + ctr, col + de);
}
}
return size;
}

You might also notice that the for loop iterates through nine cells, not eight. It includes the current cell.

We could add a line in there to not recurse if dr == 0 and de == 0. This really doesn't save us much.

We'll execute this if-statement in eight cells unnecessarily, just to avoid one recursive call. The recursive call returns immediately since the cell is marked as visited.

If you don't like modifying the input matrix, you can create a secondary visited matrix.

Arraylist<Integer> computePondSizes(int[][] land) {
boolean[][] visited = new boolean[land.length][land[0].length];
Arraylist<Integer> pondSizes = new Arraylist<Integer>();
for (int r = 0; r < land.length; r++) {
for (int c = 0; c < land[r].length; c++) {
int size = computeSize(land, visited, r, c);
if (size > 0) {
pondSizes.add(size);
}
}
}
return pondSizes;
}

int computeSize(int[][] land, boolean[][] visited, int row, int col) {
/* If out of bounds or already visited. */
if (row < 0 || col < 0 || row >= land.length || col >= land[row].length ||
visited[row][col] || land[row][col] != 0) {
return 0;
}
int size = 1;
visited[row][col] = true;
for (int dr = -1; dr <= 1; dr++) {
for (int de = -1; de <= 1; de++) {
size += computeSize(land, visited, row + dr, col + de);
}
}
return size;
}
https://segmentfault.com/a/1190000003753307

Q:如何找湖的数量呢？湖的定义是某个0，其上下左右都是同一个岛屿的陆地。A:我们可以先用Number of island的方法，把每个岛标记成不同的ID，然后过一遍整个地图的每个点，如果是0的话，就DFS看这块连通水域是否被同一块岛屿包围，如果出现了不同数字的陆地，则不是湖。

    public int numberOfLakes(int[][] world){
        int islandId = 2;
        for(int i = 0; i < world.length; i++){
            for(int j = 0; j < world[0].length; j++){
                if(world[i][j] == 1){
                    findIsland(world, i, j, islandId);
                    islandId++;
                }
            }
        }
        int lake = 0;
        for(int i = 0; i < world.length; i++){
            for(int j = 0; j < world[0].length; j++){
                if(world[i][j] == 0){
                    // 找到当前水域的邻接陆地编号
                    int currId = 0;
                    if(i > 0) currId = (world[i - 1][j] != 0 ? world[i - 1][j] : currId);
                    if(j > 0) currId = (world[i][j - 1] != 0 ? world[i][j - 1] : currId);
                    if(i < world.length - 1) currId = (world[i + 1][j] != 0 ? world[i + 1][j] : currId);
                    if(j < world[0].length - 1) currId = (world[i][j + 1] != 0 ? world[i][j + 1] : currId);
                    // 如果该点是湖，加1
                    if(findLake(world, i, j, currId)){
                        lake++;
                    }
                }
            }
        }
        return lake;
    }

http://www.1point3acres.com/bbs/thread-175393-1-1.html

numberIsland找不同形状的Island的个数
比如
1010
0100
0000
1010
0100

这样上下两个岛形状一样，return

dfs遍历的方向可以优化一下，只需要右边，右下，下，左下四个方向即可。
关于这题的做法，我们先BFS把所有的岛存下来，然后发现第一个岛的index是(0,0) -> (1,1) ->(0,2)，convert成一维坐标i*m + j是0 -> 6 -> 2，sort好了是0 -> 2 -> 6。同样的方法做第一个岛（4，0） -> (5,1) -> (4,2)， convert成一维坐标16->22->18, 然后sort一下，大家减去第一个数字又变成0->2->6 就能判断两个岛是一样了
刚刚想了下发现二维转化成一维还是有点问题的，还是直接用二维的方法比吧

举个bug的例子？
[0][1][1]
[1][0][0]
和
[1][1][1]
对所以需要加一个判断要求每层的node个数一样但这样还不如二维比算了

请问两个岛如果经过旋转或翻转之后一样应该算一个还是两个啊？
算不同的
你是指这个吗？
[0][1][1]
[1][0][0]
和
[1][1][1]
这个没有问题呢，因为是转化成了一维唯一的数，所以每一个case都可以区分
- the way to transferToKey will not work

public static int getIslandNumberWithDifferentShapes(int[][] matrix) {. 鍥磋鎴戜滑@1point 3 acres
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
. 1point 3acres 璁哄潧
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
Set<String> set = new HashSet<String>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (!visited[i][j] && matrix[i][j] == 1) {
List<Integer> path = new ArrayList<Integer>();
helper(matrix, visited, i, j, path);
String str = transferToKey(path);.鏈枃鍘熷垱鑷�1point3acres璁哄潧
set.add(str);
}
}
}
return set.size();
}. Waral 鍗氬鏈夋洿澶氭枃绔�,
private static String transferToKey(List<Integer> path) {
StringBuilder sb = new StringBuilder();. from: 1point3acres.com/bbs
int diff = path.get(0) - 0;-google 1point3acres
for (int i : path) {. visit 1point3acres.com for more.
sb.append((i - diff) + "#");
}.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
return sb.toString();
}
private static void helper(int[][] matrix, boolean[][] visited, int x,
int y, List<Integer> path) {
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || visited[x][y] || matrix[x][y] != 1) {
return;
}. 1point 3acres 璁哄潧
int n = matrix[0].length;
int[] dx = {1, -1, 0, 0, 1, 1, -1, -1};. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
int[] dy = {0, 0, 1, -1, 1, -1, 1, -1};. From 1point 3acres bbs
visited[x][y] = true;
path.add((x * n + y));
for (int i = 0; i < dx.length; i++) {
int nx = dx[i] + x;
int ny = dy[i] + y;
helper(matrix, visited, nx, ny, path);
}
}

http://www.geeksforgeeks.org/find-number-of-islands/
http://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/

Consider a matrix with rows and columns, where each cell contains either a ‘0’ or a ‘1’ and any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally .If one or more filled cells are also connected, they form a region. find the length of the largest region.

Examples:

Input : M[][5] = { 0 0 1 1 0
                   1 0 1 1 0
                   0 1 0 0 0
                   0 0 0 0 1 }
Output : 6 
Ex: in the following example, there are 2 regions one with length 1 and the other as 6.
    so largest region : 6

A cell in 2D matrix can be connected to at most 8 neighbors. So in DFS, we make recursive calls for 8 neighbors. We keep track of the visited 1’s in every DFS and update maximum length region.

int isSafe(int M[][COL], int row, int col,

           bool visited[][COL])

{

    // row number is in range, column number is in

    // range and value is 1 and not yet visited

    return (row >= 0) && (row < ROW) &&

           (col >= 0) && (col < COL) &&

           (M[row][col] && !visited[row][col]);

}

// A utility function to do DFS for a 2D boolean

// matrix. It only considers the 8 neighbours as

// adjacent vertices

void DFS(int M[][COL], int row, int col,

         bool visited[][COL], int &count)

{

    // These arrays are used to get row and column

    // numbers of 8 neighbours of a given cell

    static int rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1};

    static int colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1};

    // Mark this cell as visited

    visited[row][col] = true;

    // Recur for all connected neighbours

    for (int k = 0; k < 8; ++k)

    {

        if (isSafe(M, row + rowNbr[k], col + colNbr[k],

                                              visited))

        {

            // increment region length by one

            count++;

            DFS(M, row + rowNbr[k], col + colNbr[k],

                                    visited, count);

        }

    }

}

// The main function that returns largest  length region

// of a given boolean 2D matrix

int  largest(int M[][COL])

{

    // Make a bool array to mark visited cells.

    // Initially all cells are unvisited

    bool visited[ROW][COL];

    memset(visited, 0, sizeof(visited));

    // Initialize result as 0 and travesle through the

    // all cells of given matrix

    int result  = INT_MIN;

    for (int i = 0; i < ROW; ++i)

    {

        for (int j = 0; j < COL; ++j)

        {

            // If a cell with value 1 is not

            if (M[i][j] && !visited[i][j])

            {

                // visited yet, then new region found

                int count = 1 ;

                DFS(M, i, j, visited , count);

                // maximum region

                result = max(result , count);

            }

         }

    }

    return result ;

}

http://www.cnblogs.com/EdwardLiu/p/6288850.html
Find largest island in a board

 4     public int findLargestIsland(int[][] board) {
 5         if (board==null || board.length==0 || board[0].length==0) return 0;
 6         int m = board.length;
 7         int n = board[0].length;
 8         int maxArea = 0;
 9         for (int i=0; i<m; i++) {
10             for (int j=0; j<n; j++) {
11                 if (board[i][j] != 1) continue;
12                 int area = 0;
13                 area = dfs(board, i, j, m, n);
14                 maxArea = Math.max(maxArea, area);
15             }
16         }
17         return maxArea;
18     }
19     
20     
21     public int dfs(int[][] board, int i, int j, int m, int n) {
22         if (i<0 || i>=m || j<0 || j>=n || board[i][j]!=1) return 0;
23         int area = 1;
24         board[i][j] = 2;
25         area += dfs(board, i-1, j, m, n);
26         area += dfs(board, i+1, j, m, n);
27         area += dfs(board, i, j-1, m, n);
28         area += dfs(board, i, j+1, m, n);
29         return area;
30     }

Read full article from Find the number of islands | GeeksforGeeks

Leetcode 200: Find the number of islands

Labels

Popular Posts