洛谷:P1950:长方形


洛谷:P1950:长方形

题目

P1950:长方形

分析

这道题目和P4147:玉蟾宫非常相像,不过后者是求面积,这里是求可以切割出的矩形的计数。这会造成一些小小的差异。

确定高度

我们设置一个全局变量heights[i][j]去存储:对于格子(i, j),它的高度。这个高度是后续单调栈找左右边界时的核心。

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        if (grid[i][j] == '*')  // *表示用过了,或者说障碍
        {
            heights[i][j] = 0;
        }
        else
        {
            heights[i][j] = heights[i - 1][j] + 1;
        }
    }
}

单调栈确定左右边界

用单调栈来确定格子(i, j)由于相应高度限制而能到达的左右边界。这里和P4147:玉蟾宫开始出现细微的差异,体现在左右边界的判定上。

先讨论两个例题中左边界的计算。

//4147中的计算
for (int j = 0; j < m; ++j)
{
    while (!s.empty() && heights[i][s.top()] >= heights[i][j])
    {
        s.pop();
    }
    left[j] = s.empty() ? 0 : s.top() + 1;
    s.push(j);
}

其逻辑是:只要栈顶的高度不小于当前的高度,就表明可以继续往左拓展(也就是画出的矩形的左边界可以往左)。而一旦小于当前高度,j列的左边界拓展就戛然而止,因此此时的左边界是栈顶+1。

//1950中的计算
for (int j = 1; j <= m; j++)
{
    while (!s.empty() && heights[i][s.top()] >= heights[i][j])
    {
        s.pop();
    }
    if (s.empty())
    {
        left_border[j] = 0;
    }
    else
    {
        left_border[j] = s.top();
    }
    s.push(j);
}

它的额逻辑和4147基本类似,但是左边界不用+1。这体现在后续的面积计算上。

在计算右边界的时候:

//4147中的计算
for (int j = m - 1; j >= 0; --j)
{
    while (!s.empty() && heights[i][s.top()] >= heights[i][j])
    {
        s.pop();
    }
    right[j] = s.empty() ? m : s.top();
    s.push(j);
}

右边界是最后一个不低于j列高度的单元格,和题目要求一致。

//1950中的计算
for (int j = m; j >= 1; j--)
{
    while (!s2.empty() && heights[i][s2.top()] > heights[i][j])
    {
        s2.pop();
    }
    if (s2.empty())
    {
        right_border[j] = m + 1;
    }
    else
    {
        right_border[j] = s2.top();
    }
    s2.push(j);
}

注意heights[i][s2.top()] > heights[i][j]这里用到了>而不是>=

总结一下,在本题中:

  • 左边界使用>=确保相同高度的列只有最左边的那个会被计算。
  • 右边界使用>确保相同高度的列只有最右边的那个会被计算。

这种不对称处理确保了每个可能的矩形只被计算一次,避免了重复计算,对本题这种需要计算所有可能矩形数量的问题非常关键。

划分矩形数量

(i, j)这个格子出发,高度有heights[i][j]中选择,向左有j-left_border[j]种选择,向右有right_border[j]-j种选择。所以总的方式是:\(ans+=heights[i][j]\times(right\_border[j]-j)\times(j-left\_border[j]);\)

答案

Solution

思考

(略)

Previous Next