程序设计II上机实验10B："完美阴阳矩阵"

“完美阴阳矩阵”

Time limit: 1000 ms

Memory limit: 256 MB

Standard I/O

Content

$定义元素全为0或1的矩阵为“阴阳矩阵”，即一个n行m列的矩阵A为“阴阳矩阵”当且仅当：$

$\forall i\forall j(A_{ij}\in {0,1})(1≤i≤n,1≤j≤m)$

$对于一个n行m列的矩阵A和一个n’行m’列(1≤n’≤n,1≤m’≤m)的矩阵A’，称A’为A的子矩阵当且仅当：$

$\exists i_0\exists j_0\forall i\forall j(A_{i_0+i,j_0+j}=A’_{ij}(1≤i≤n’,1≤j≤m’,0≤i_0≤n−n’,0≤j_0≤m−m’))$

$自然地，“阴阳矩阵”的子矩阵也是“阴阳矩阵”。$

$对一个n行m列的“阴阳矩阵”矩阵A，称它为“完美阴阳矩阵”当且仅当以下两个条件都成立：$

$1.\forall i\forall j(A_{i,j}≠A_{i,j+1})(1≤i≤n,1≤j≤m−1)$

$2.\forall i\forall j(A_{i,j}≠A_{i+1,j})(1≤i≤n−1,1≤j≤m)$

$显然，一个n行m列的矩阵的元素个数为n×m.现给定一个n行m列的“阴阳矩阵”A，$

$1.求“阴阳矩阵”A的子方阵（行与列数目相同的子矩阵）中元素最多的“完美阴阳方阵”，输出该子方阵的元素数目。$

$2.求“阴阳矩阵”A的子矩阵中元素最多的“完美阴阳矩阵”，输出该子矩阵的元素数目。$

Input Description

输入的第一行是两个空格隔开的整数n和m，分别表示矩阵的长和宽。接下来的n行，每行m个数，空格隔开，表示一个n×m的阴阳矩阵。

Output Description

两行，每行一个数，表示所求答案。

Sample

INPUT

3 3
1 0 1
0 1 0
1 0 0

OUTPUT

4
6

Hint

对于20%20%的数据，n,m≤80n,m≤80

对于40%40%的数据，n,m≤400n,m≤400

对于100%100%的数据，n,m≤2000n,m≤2000（各种暴力方法都会超时哦）

Code

#include <stdio.h>
#include <stdlib.h>
typedef struct intervaldata{
    int begin;
    int end;
    struct intervaldata *next;
}Interval;//区间
Interval** allhead;
int m,n;
int MaxSquareLen,MaxRectArea;//最大方阵的边长，最大矩阵的面积()
int max(int a,int b){
    return a>b?a:b;
}
int min(int a,int b){
    return a<b?a:b;
}
Interval* MakeNode(int begin,int end){
    Interval* p=(Interval*)malloc(sizeof(Interval));
    p->begin=begin;
    p->end=end;
    p->next=NULL;
    return p;
}
void UpdateMaxRectArea(int weith,int depth){//更新矩阵最大值,注意到阴阳矩阵应该比普通矩阵长宽各+1
    MaxRectArea=max(MaxRectArea,(weith+1)*(depth+1));
    MaxSquareLen=max(MaxSquareLen,min(weith,depth)+1);
}
int Search(int row,int left,int right,int depth){//row是当前行
    //depth表示当前矩形纵深高度(占的行数，不包括当前行)
    //left,right是上一行传递下来的区间范围
    if(row>=m-1){//超出地图了，地图最后一行是m-2（全地图化为普通矩阵后共m-1行）;
        UpdateMaxRectArea(right-left+1,depth);
        return 1;
    }
    Interval* p=allhead[row]->next;
    int tmpleft,tmpright;
    while(p!=NULL){
        if(p->end<left){
                p=p->next;
                continue;
        } 
        if(p->begin>right) break;
        tmpleft=max(left,p->begin);
        tmpright=min(right,p->end);
        Search(row+1,tmpleft,tmpright,depth+1);
        p=p->next;
    }
    //结算
    UpdateMaxRectArea(right-left+1,depth);
    return 1;
}
int main(){
    int i,j;
    scanf("%d%d",&m,&n);
    int **map=(int **)malloc(sizeof(int *)*m);
    for(i=0;i<m;i++){
        map[i]=(int *)malloc(sizeof(int)*n);
        for(j=0;j<n;j++){
            scanf("%d",&map[i][j]);
        }
    }
    allhead=(Interval**)malloc(sizeof(Interval*)*(m-1));//每一行的头结点指针
    for(i=0;i<m-1;i++){//化为普通0/1矩阵，同时求出每行的值为1区间存在链表里,问题化为求解最大1矩阵面积
        int start=-1;
        allhead[i]=MakeNode(0,0);//头结点不用
        Interval* now=allhead[i];
        for(j=0;j<n-1;j++){
            if(map[i][j+1]==!map[i][j] && map[i+1][j]==!map[i][j] && map[i+1][j+1]==map[i][j]){
                map[i][j]=1;
                if(start==-1) start=j;
            }
            else{
                map[i][j]=0;
                if(start!=-1){
                    Interval* p=MakeNode(start,j-1);
                    now->next=p;
                    now=p;
                    start=-1;
                }
            }
        }
        if(start!=-1){
            Interval* p=MakeNode(start,j-1);
            now->next=p;
        }
    }
    for(i=0;i<m-1;i++){//遍历每一行的区间
        Interval* p=allhead[i]->next;
        while(p!=NULL){
            Search(i+1,p->begin,p->end,1);
            p=p->next;
        }
    }
    printf("%d\n%d",MaxSquareLen*MaxSquareLen,MaxRectArea);
    for(i=0;i<m;i++){
        free(map[i]);
    }
    free(map);
    for(i=0;i<m-1;i++){
        Interval* p=allhead[i];
        while(p!=NULL){
            allhead[i]=p->next;
            free(p);
            p=allhead[i];
        }
    }
    return 0;
}