洛谷P1169棋盘制作题解报告

小咪咪 2023-07-07 03:54 3阅读 0赞

# 一、题目 #

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

# 二、分析 #

以样例中的数据为例，格子共有三行三列。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaXNodV96aGVuZw_size_16_color_FFFFFF_t_70]  
咱们可以按顺序枚举每个格子。求长方形的时候，可以枚举整行。求正方形的时候，要以当前的格子作为正方形右下角的格子。  
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值 ##

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

## （二）计算right值 ##

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

## （三）计算up值 ##

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

# 三、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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaXNodV96aGVuZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200220205145305.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaXNodV96aGVuZw==,size_16,color_FFFFFF,t_70