洛谷P1169棋盘制作题解报告

一、题目

https://www.luogu.com.cn/problem/P1169

二、分析

以样例中的数据为例，格子共有三行三列。

咱们可以按顺序枚举每个格子。求长方形的时候，可以枚举整行。求正方形的时候，要以当前的格子作为正方形右下角的格子。
i = 1, j = 1时，矩形的宽度是3，高度是1，则矩形的面积是3，如图A的整个图形所示。以第一行第一列作为右下角格子的最大正方形的边长是1，则最大正方形的面积是1，如图B中的绿色部分所示。
i = 1, j = 2时，矩形的宽度是3，高度是1，则矩形的面积是3，如图B的整个图形所示。以第一行第二列作为右下角格子的最大正方形的边长是1，则最大正方形的面积是1，如图B中的绿色部分所示。
i = 1, j = 3时，矩形的宽度是3，高度是1，则矩形的面积是3，如图C的整个图形所示。以第一行第三列作为右下角格子的最大正方形的边长是1，则最大正方形的面积是1，如图C中的绿色部分所示。
i = 2, j = 1时，矩形的宽度是3，高度是2，则矩形的面积是6，如图D的整个图形所示。以第二行第一列作为右下角格子的最大正方形的边长是1，则最大正方形的面积是1，如图D中的绿色部分所示。
i = 2, j = 2时，矩形的宽度是3，高度是2，则矩形的面积是6，如图E的整个图形所示。以第二行第二列作为右下角格子的最大正方形的边长是2，则最大正方形的面积是4，如图E中的绿色部分所示。
……

具体编程时，咱们可设三个二维数组：left[i][j]，right[i][j]和up[i][j]。用来表示第i行第j列格子可向左、向右、向上延伸的极限值。根据棋盘规则，只有相邻的两个格子颜色不同才能延伸过去。

（一）计算left值

left值	意义
left[1][1]=1	第一行第一列的格子，因为是左边界格子，不能往左延伸，只能停留在本格子上。
left[1][2]=1	第一行第二列的格子，因为颜色与第一行第一列的格子不同，所以最左侧可延伸到第一列。
left[1][3]=1	因为第一行第三列格子相邻的颜色两两不相同，所以第一行第三列格子向左可延伸到第一列。
left[2][1]=1	第二行第一列的格子，因为是左边界格子，不能往左延伸，只能停留在本格子上。
left[2][2]=1	第二行第二列的格子，因为颜色与第二行第一列的格子不同，所以向左可延伸到第一列。
left[2][3]=1	因为第二行三列格子相邻的颜色两两不相同，所以第二行三列格子向左可延伸到第一列。
left[3][1]=1	第三行第一列的格子，因为是左边界格子，不能往左延伸，只能停留在本格子上。
left[3][2]=1	第三行第二列的格子，因为颜色与第三行第一列的格子不同，所以向左可延伸到第一列。
left[3][3]=3	第三行第三列的格子与第三行第二列的格子颜色相同，所以第三行第三列格子不能往左延伸，只能停留在本格子上。

（二）计算right值

right值	意义
right[1][1]=3	第一行的三个格子颜色两两不同，所以第一行第一列的格子可以向右延伸到第一行第三列。
right[1][2]=3	第一行第二列的格子，因为颜色与第一行第三列的格子不同，所以可以向右延伸到第一行第三列。
right[1][3]=3	第一行第三列的格子处于右边界，不能再向右延伸。
right[2][1]=3	第二行的三个格子颜色两两不同，所以第二行第一列的格子可以向右延伸到第二行第三列。
right[2][2]=3	第二行第二列的格子，因为颜色与第二行第三列的格子不同，所以可以向右延伸到第二行第三列。
right[2][3]=3	第二行第三列的格子处于右边界，不能再向右延伸。
right[3][1]=2	第三行第一列格子颜色与第二列格子颜色不同，所以可延伸到第二列；第二列颜色与第三列相同，所以不能延伸到第三列。
right[3][2]=2	第三行第二列的格子，因为颜色与第三行第三列的格子不同，所以不能延伸到第三列。
right[3][3]=3	第三行第三列的格子处于右边界，不能再向右延伸。

（三）计算up值

up值	意义
up[1][1]=1	第一行第一列处于上边界，则此格子的高度为1
up[1][2]=1	第一行第二列处于上边界，则此格子的高度为1
up[1][3]=1	第一行第三列处于上边界，则此格子的高度为1
up[2][1]=2	第二行第一列的颜色与第一行第一列不同，则竖直方向两个格子的累积高度为2
up[2][2]=2	第二行第二列的颜色与第一行第二列不同，则竖直方向两个格子的累积高度为2
up[2][3]=2	第二行第三列的颜色与第一行第三列不同，则竖直方向两个格子的累积高度为2
up[3][1]=3	第一列的三个格子相邻颜色都不同，所以枚举到第三行第一列时，竖直方向三个格子的累积高度为3
up[3][2]=3	第二列的三个格子相邻颜色都不同，所以枚举到第三行第二列时，竖直方向三个格子的累积高度为3
up[3][3]=1	第三行第三列格子的颜色与第二行第三列相同，不能向上延伸。所以枚举到第三行第三列时，竖直方向格子的高度为1。

三、AC代码

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 2005;

int a[maxn][maxn], lef[maxn][maxn], righ[maxn][maxn], up[maxn][maxn];
int n, m, area1, area2;

int main()
{
    //freopen("P1169.in", "r", stdin);

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
            //初始化
            lef[i][j] = righ[i][j] = j;
            up[i][j] = 1;
        }
    }

    //格子(i,j)往左最多能达到哪一列
    for(int i = 1; i <= n; i++)
    {
        for(int j = 2; j <= m; j++)
        {
            if(a[i][j] != a[i][j-1])
            {
                lef[i][j] = lef[i][j-1];
            }
        }
    }

    //格子(i,j)往右最多能达到哪一列
    for(int i = 1; i <= n; i++)
    {
        for(int j = m - 1; j > 0;j--)
        {
            if(a[i][j] != a[i][j+1])
                {
                    righ[i][j] = righ[i][j+1];
                }
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(i > 1 && a[i][j] != a[i-1][j])//相同列上下行格子颜色不同
            {
                lef[i][j] = max(lef[i][j], lef[i-1][j]);    //取本行和上一行的交集，用max
                righ[i][j] = min(righ[i][j], righ[i-1][j]); //取本行和上一行的交集，用min
                up[i][j] = up[i-1][j] + 1;
            }

            int width = righ[i][j] - lef[i][j] + 1; //求宽度，左右端点都要算进去，所以要加1
            int side = min(width, up[i][j]);        //在宽度和高度之间取最小值作为边长
            area1 = max(area1, side * side);        //正方形面积
            area2 = max(area2, width * up[i][j]);   //长方形面积
        }
    }

    cout << area1 << endl << area2;

    return 0;
}

=======================================
了解信息学奥赛请加微信307591841或QQ群581357582