title: 二维矩阵查询算法(岛屿问题)
date: 2022-04-06 09:08:55.753
updated: 2022-04-06 09:09:04.314
url: https://ritoom.me/archives/二维矩阵查询算法岛屿问题
categories:

• Code
• Note
  tags:
• java

• note

需求

需要求出一个二维矩阵中大于某一个值的数,并按照周围8个方向(上下左右和倾斜相邻的方向)查找并组成区域,返回区域同时携带每个点的点坐标(索引).

查找了下网上的问题,发现这个问题和leetcode中的岛屿问题很相似,解题思路也是可以套用的,只是需要根据自身情况去保存区域和区域内点的索引.

二维矩阵可以通过索引计算出一个一维数组的索引.

深度优先搜索

使用递归的方式.

问题: 遇到二维矩阵特别大的情况,会出现递归层数过深导致超出程序默认的堆栈大小,可以在程序运行时指定可使用的堆栈大小解决.

    /**
     * 深度优先搜素
     * 查找二维矩阵中区域
     * @param array 二维矩阵
     * @param num 界限值
     * @return 区域集合
     */
    public static List<List<DemMn>> FindingNeighboursInMatrix(double[][] array,int num){
        List<List<DemMn>> list = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[0].length; j++) {
                double dd = array[i][j];
                if (Math.abs(dd+1000)>=0.01d && Math.abs(dd)>num){
                    List<DemMn> demMns = findneighbours(i, j, num, array);
                    if (demMns.size() > 0){
                        list.add(demMns);
                    }
                }
            }
        }
        return list;
    }

    private static List<DemMn> findneighbours(int i, int j, int num, double[][] matrix) {
        if (i < 0 || i>=matrix.length || j<0 || j>= matrix[0].length){
            return new ArrayList<>();
        }
        double dd = matrix[i][j];
        if (Math.abs(dd+1000)<0.01d || Math.abs(dd) <= num){
            return new ArrayList<>();
        }
        List<DemMn> neb = new ArrayList<>();
        neb.add(new DemMn(i,j));
        matrix[i][j] = 0;
        //上方
        List<DemMn> d1 = findneighbours(i-1,j-1,num,matrix);
        List<DemMn> d2 = findneighbours(i-1,j,num,matrix);
        List<DemMn> d3 = findneighbours(i-1,j+1,num,matrix);
        //左
        List<DemMn> d4 = findneighbours(i,j-1,num,matrix);
        //右
        List<DemMn> d5 = findneighbours(i,j+1,num,matrix);
        //下方
        List<DemMn> d6 = findneighbours(i+1,j-1,num,matrix);
        List<DemMn> d7 = findneighbours(i+1,j,num,matrix);
        List<DemMn> d8 = findneighbours(i+1,j+1,num,matrix);

        //top element
        if (d1.size() > 0){
            neb.addAll(d1);
        }
        if (d2.size() > 0){
            neb.addAll(d2);
        }
        if (d3.size() > 0){
            neb.addAll(d3);
        }
        // left element
        if (d4.size() > 0){
            neb.addAll(d4);
        }
        // right element
        if (d5.size() > 0){
            neb.addAll(d5);
        }
        // bottom row
        if (d6.size() > 0){
            neb.addAll(d6);
        }
        if (d7.size() > 0){
            neb.addAll(d7);
        }
        if (d8.size() > 0){
            neb.addAll(d8);
        }
        return neb;
    }

广度优先搜索

使用队列的方式.

    /**
     * 广度优先搜索
     * 查找二维矩阵中的区域
     * @param array 二维矩阵数组
     * @param num 界限值
     * @return 区域集合
     */
    public static List<List<DemMn>> getNearArea(double[][] array,float num){
        BigDecimal bigDecimal = new BigDecimal(String.valueOf(num));
        List<List<DemMn>> list = new ArrayList<>();
        int nr = array.length;
        int nc = array[0].length;

        for (int r = 0; r < nr; r++) {
            for (int c = 0; c < nc; c++) {
                double dd = array[r][c];
                if (Math.abs(dd+1000)>=0.01d && bigDecimal.compareTo(new BigDecimal(Math.abs(dd))) > 0){
                    List<DemMn> demMns = new ArrayList<>();
                    demMns.add(new DemMn(r,c));
                    array[r][c] = 0;
                    Queue<Integer> queue = new LinkedList<>();
                    queue.add(r*nc+c);
                    while (!queue.isEmpty()){
                        int index = queue.remove();
                        int row = index/nc;
                        int col = index%nc;
                        if (row-1>=0 && col-1>=0 && Math.abs(array[row-1][col-1]+1000)>=0.01d && Math.abs(array[row-1][col-1]) > num){
                            demMns.add(new DemMn(row-1,col-1));
                            queue.add((row-1)*nc+(col-1));
                            array[row-1][col-1] = 0;
                        }
                        if (row-1>=0 && Math.abs(array[row-1][col]+1000)>=0.01d && Math.abs(array[row-1][col]) > num){
                            demMns.add(new DemMn(row-1,col));
                            queue.add((row-1)*nc+col);
                            array[row-1][col] = 0;
                        }
                        if (row-1>=0 && col+1<nc && Math.abs(array[row-1][col+1]+1000)>=0.01d && Math.abs(array[row-1][col+1]) > num){
                            demMns.add(new DemMn(row-1,col+1));
                            queue.add((row-1)*nc+(col+1));
                            array[row-1][col+1] = 0;
                        }
                        if (col-1>=0&&Math.abs(array[row][col-1]+1000)>=0.01d&&Math.abs(array[row][col-1]) > num){
                            demMns.add(new DemMn(row,col-1));
                            queue.add(row*nc+col-1);
                            array[row][col-1] = 0;
                        }
                        if (col+1<nc&&Math.abs(array[row][col+1]+1000)>=0.01d&&Math.abs(array[row][col+1]) > num){
                            demMns.add(new DemMn(row,col+1));
                            queue.add(row*nc+col+1);
                            array[row][col+1] = 0;
                        }
                        if (row+1<nr && col-1>=0 && Math.abs(array[row+1][col-1]+1000)>=0.01d && Math.abs(array[row+1][col-1]) > num){
                            demMns.add(new DemMn(row+1,col-1));
                            queue.add((row+1)*nc+col-1);
                            array[row+1][col-1] = 0;
                        }
                        if (row+1<nr && Math.abs(array[row+1][col]+1000)>=0.01d && Math.abs(array[row+1][col]) > num){
                            demMns.add(new DemMn(row+1,col));
                            queue.add((row+1)*nc+col);
                            array[row+1][col] = 0;
                        }
                        if (row+1<nr && col+1<nc && Math.abs(array[row+1][col+1]+1000)>=0.01d && Math.abs(array[row+1][col+1]) > num){
                            demMns.add(new DemMn(row+1,col+1));
                            queue.add((row+1)*nc+col+1);
                            array[row+1][col+1] = 0;
                        }
                    }
                    list.add(demMns);
                }
            }
        }
        return list;
    }

相关类

public class DemMn {
    private int angleCount;
    private int distanceCount;
}