棋盘

ゞ浴缸里的玫瑰 2022-04-24 11:38 216阅读 0赞

【问题描述】

棋盘是指一个行和列编号从1~N的NxN的二进制矩阵，当行号和列号之和为偶数时该矩阵对应位置为黑色的(1)，否则为白色的(0)。以下图示为N=1、2、3时的棋盘。

![151123141390500455413.jpg][]

給出一个NxN的二进制矩阵，请找出位于该矩阵内的最大尺寸的完整棋盘，以及最大尺寸棋盘的数量（棋盘可以交叠）。

【输入形式】

每个测试用例的第一行是一个正整数N(1<=N<=2000)，表示給定矩阵的行数和列数，接下来的N行描述了这个矩阵：每行有N个字符，既可以是“1”（代表黑块），也可以是“0”（代表白块）。矩阵至少包含一个“1”字符。

【输出形式】

输出最大尺寸棋盘的行列的大小，以及最大棋盘的个数，以空格分隔。

【样例输入】

5
    00101
    11010
    00101
    01010
    11101

【样例输出】

3 3

\#include<iostream>  
using namespace std;  
int main()\{  
    int n;  
    cin>>n;  
    int i,j,k,j1,k1=0,t,ok1,ok=0,s=0;  
    char z\[n\]\[n\];   
    for(i=0;i<n;i++)\{  
        for(j=0;j<n;j++)\{  
            cin>>z\[i\]\[j\];  
        \}  
    \}  
    for(i=1;i<=n;i++)\{  
        for(j=0;j<i;j++)\{  
            for(k=0;k<i;k++)\{  
                if(z\[j\]\[k\]=='0') continue;  
                ok1=1;  
                for(j1=j;j1<n-i+1+j;j1++)\{  
                    t=(j1-j+1)%2;  
                    for(k1=k;k1<n-i+1+k;k1++)\{  
                        if(z\[j1\]\[k1\]=='1')\{  
                            if(t==0)\{  
                                ok1=0;  
                                break;  
                            \}   
                            t=0;  
                        \}  
                        else if(z\[j1\]\[k1\]=='0')\{  
                            if(t==1)\{  
                               ok1=0;  
                               break;  
                            \}  
                            t=1;  
                        \}  
                    \}  
                    if(ok1==0) break;  
                \}  
                if(j1==n-i+1+j&&k1==n-i+1+k)\{  
                    ok=1;  
//                    for(j1=j;j1<n-i+1+j;j1++)\{  
//                        for(k1=k;k1<n-i+1+k;k1++)  
//                    cout<<z\[j1\]\[k1\]<<' ';  
//                    cout<<endl;  
//                    \}  
//                    cout<<"\_\_\_\_\_\_\\n";  
                      
                    s++;  
                \}  
            \}  
        \}  
        if(ok==1) break;  
    \}  
    if(ok==1) cout<<n-i+1<<' '<<s;  
\}

[151123141390500455413.jpg]: http://115.157.200.135/userfiles/image/151123141390500455413.jpg