Thursday, 30 January 2014

Maximum size square sub-matrix with all 1s

Java Implementation:

import java.util.Scanner;

public class MaxSizeSquareSubMatrix {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int rows=0,columns=0;
        rows=sc.nextInt();
        columns = sc.nextInt();
        int [][]array=new int[rows][columns];
        for(int index=0;index<rows;index++)
        {
            for(int subIndex=0;subIndex<columns;subIndex++)
            {
                array[index][subIndex]=sc.nextInt();
            }
        }
        printMaxSubArray(array,rows,columns);
        sc.close();
    }

    // funtion to print max square sub array in a matrix
    private static void printMaxSubArray(int[][] array, int rows, int columns) {
       
        int countArray[][]=new int[rows][columns];
        int max_countArray=0;
        int max_row=0,max_column=0,outer=0,inner=0;
       
        // set the first row of countArray
        for(int rowIndex=0;rowIndex<rows;rowIndex++)
        {
            countArray[rowIndex][0]=array[rowIndex][0];
        }
       
        // set the first column of countArray
        for(int colIndex=0;colIndex<columns;colIndex++)
        {
            countArray[0][colIndex]=array[0][colIndex];
        }
       
        // calculate the other values of countArray
        for(outer=1;outer<rows;outer++)
        {
            for(inner=1;inner<columns;inner++)
            {
                if(array[outer][inner]==1)
                {
                   
                    countArray[outer][inner]=min(countArray[outer][inner-1],
                            countArray[outer-1][inner],countArray[outer-1][inner-1])+1;
                }
                else
                {
                    countArray[outer][inner]=0;
                }
            }
        }
       
        // calculate the max value in countArray and its corresponding row and column index
        max_countArray=countArray[0][0];
        for(outer=0;outer<rows;outer++)
        {
            for(inner=0;inner<columns;inner++)
            {
                if(max_countArray<countArray[outer][inner])
                {
                    max_countArray=countArray[outer][inner];
                    max_row=outer;
                    max_column=inner;
                }
            }
        }
       
       
        // print the max sub array
       
        for(outer=max_row;outer>max_row-max_countArray;outer--)
        {
            for(inner=max_column;inner>max_column-max_countArray;inner--)
            {
                System.out.print(array[outer][inner] + " ");
            }
            System.out.println();
        }
    }

    // utility method to get minimum among three numbers
   
    private static int min(int a, int b, int c) {
        int min=a;
        if(min>b)
        {
            min=b;
        }
        if(min>c)
        {
            min=c;
        }
        return min;
    }

}

No comments:

Post a Comment