Friday, September 13, 2013

find submatrix with non zero element for a given matrix

 static void findSubMatix(int[][] mat, int size) {
        int imax = 0, jmax = 0, res = 1;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                int d = 0, r = 0, max = 1;
                while (max + i < size && j + max < size) {
                    if (mat[i + max][j] == 1 && mat[i][j + max] == 1) {
                        max++;
                    } else {
                        break;
                    }
                }
                int x = max - 1;
                d = i + max - 1;
                r = j + max - 1;
                if (mat[d][r] == 1) {
                    x--;
                    while (x > 0) {
                        if (mat[d - x][r] == 1 && mat[d][r - x] == 1) {
                            x--;
                        } else {
                            break;
                        }
                    }
                }
                if (x == 0 && res < max) {
                    res = max;
                    imax = i;
                    jmax = j;
                }
            }
        }
        System.out.println("\nsize :" + res + "(" + imax + "," + jmax + ")");
        for (int a = imax; a <= imax + res - 1; a++) {
            System.out.println();
            for (int b = jmax; b <= jmax+res-1; b++) {
                System.out.print(mat[a][b]+" , ");
            }
        }
    }

    static public void main(String[] args) {
        int[][] mat = {
            {1, 0, 1, 1, 1, 0, 0, 1},
            {1, 1, 1, 1, 0, 1, 1, 1},
            {1, 1, 1, 1, 1, 1, 1, 1},
            {0, 1, 1, 0, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 1},
            {1, 1, 1, 1, 0, 0, 0, 1},
            {1, 1, 1, 1, 1, 1, 1, 1},
            {1, 1, 1, 1, 1, 1, 1, 1}
        };
        findSubMatix(mat, 8);
    }

No comments:

Post a Comment