请设计一个高效算法,找到四条边颜色相同的最大子方阵。

原创
2016/11/29 09:23
阅读数 123

有一个方阵,其中每个单元(像素)非黑即白(非0即1),请设计一个高效算法,找到四条边颜色相同的最大子方阵。

给定一个01方阵mat,同时给定方阵的边长n,请返回最大子方阵的边长。保证方阵边长小于等于100。

测试样例:

[[1,1,1],[1,0,1],[1,1,1]],3
返回:3

 


  int maxSubMatrix(vector<vector<int> > mat, int n)   
    {  
        // write code here  
        //选定最大子方阵的边长,选择顶点,判断是合法  
        int maxlength=n;  
        while(maxlength)  //选择边长  
        {  
            for(int i=0;i<=n-maxlength;i++)  
            {  
                for(int j=0;j<=n-maxlength;j++)  
                {  
                    //当前顶点为[i,j];  
                    int key=mat[i][j];  
                    //判断是否合法  
                    bool flag=true;  
                    for(int k=0;k<maxlength;k++)  
                    {  
                        int k1=mat[i][j+k];  
                        int k2=mat[i+maxlength-1][j+k];  
                        int k3=mat[i+k][j];  
                        int k4=mat[i+k][j+maxlength-1];  
                        if(k1!=key||k2!=key||k3!=key||k4!=key)  
                        {  
                            flag=false;  
                            break;  
                        }  
                    }  
                    if(flag)  
                        return maxlength;  
                }  
            }  
            maxlength--;  
        }  
        return 0;  
    }

 

扩展:

给定一个由0,1组成的n*n方阵(n在运行时提醒用户输入),判断其中由全1组成的最大子方阵的左上角位置和阶数。例如用户输入n为5,随机产生的方阵如下:

程序的输出为:最大子方阵位于(2,2),阶数3。

要求编写方法实现上述功能,返回值是一个包含3个元素的数组,依次表示行下标,列下标,阶数。

方法原型:public static int[] findLargestBlock(int[][] m)

                                             

 

public class MaxSubMatrix {  
    public static void main(String[] args) {  
        Scanner input=new Scanner(System.in);  
        System.out.println("请输入方阵维数n:");  
        int n=input.nextInt();  
        int [][] m=new int[n][n];  
        int []a=new int[3];  
        //产生一个n*n矩阵,元素为0或1并输出  
        for(int i=0;i<n;i++){  
            for(int j=0;j<n;j++){  
                m[i][j]=(int)(Math.random()*10)%2;        
                System.out.print(m[i][j]+"\t");  
            }  
            System.out.print("\n");  
        }  
        a=findLargestBlock(m);  
        System.out.print("\n");  
        System.out.println("最大子方阵位于:("+a[0]+","+a[1]+")");  
        System.out.println("阶数:"+a[2]);  
    }  
    //找到最大的全为1的矩阵块  
    public  static int[] findLargestBlock(int [][] m){  
        boolean t=true;  
        int []a=new int[3];  
        int n=m.length;  
        int i=0,j=0,l=0;  
        for(l=n;l>=1;l--){ //矩阵维数,从最大开始 

for(i=0;i<=n-l;i++){  
                for(j=0;j<=n-l;j++){  
                    t=true;  
                    for(int x=i;x<i+l;x++){  
                        for(int y=j;y<j+l;y++){  
                            if(m[x][y]!=1){    //不为1退出此轮循环  
                                t=false;  
                                break;  
                            }  
                        }  
                        if(t==false) break;  
                    }  
                    if(t==true) break;  
                }  
                if(t==true) break;  
            }  
            if(t==true) break;  
        }  
        a[0]=i;  
        a[1]=j;  
        a[2]=l;  
        return a;  
    }   

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部