二维矩阵中Connected Cell问题(DFS)

HackerRank上面对Matrix中Connected Cell的模板, Leetcode中此类问题有island的个数,面积,surrounded regions等

dfs

public class Solution {
    public int getBiggestRegion(int[][] matrix) {
        int maxRegion = 0;
        int row = matrix.length, col = matrix[0].length;
        //boolean[][] visited = new boolean[row][col]; 

        for(int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 1) { // 找到'1'岛屿
                    int size = getRegionSize(matrix, i, j);
                    maxRegion = Math.max(size, maxRegion);
                }
            }
        }
        return maxRegion;
    }

    public int getRegionSize(int[][] matrix, int row, int col) {
        // 1. boundary checks
        if (row < 0 || col < 0 || row >= matrix.length || col >= matrix.length){
            return 0;
        }
        // 2. check if it is the region
        if (matrix[row][col] == 0) {
            return 0;
        }
        matrix[row][col] = 0; // visited check, 也可以用一个visited数组来实现
        int size = 1; // initialize size is 1
        // explore 4 directions: left, right, up, down
        public int[] rowDir = new int[]{-1, 0, 1, 0};
        public int[] colDir = new int[]{0, -1, 0, 1};
        for (int i = 0; i < 4; i++) {
            int newRow = row + rowDir[i];
            int newCol = col + colDir[i];
            if (newRow == row || newCol == col) continue; // 避免搜索自己
            size += getRegionSize(matrix, newRow, newCol);
        }
        matrix[row][col] = 1; // 搜索完了, 赋原有值
        return size;
    }


}

DFS四个方向搜索的时候,另一种写法

for (int r = row - 1; r <= row + 1; r++) {
    for (int c = col - 1: c <= col + 1; c++) {

    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s