---
title: "城市游戏"
created: 2025-11-28
tags:
  - 算法
---

# 城市游戏

## 题目 [城市游戏](https://www.acwing.com/problem/content/154/)

![[image-a89a419a.png]]

## 思路分析

就是 [[最大矩形|最大矩形]] 先把rf变成01就行了

![[image-71a53bf3.png]]

怎么处理成这样

读入时 是F就读1

也可以同时处理成第二状态

是1 就变成上面的那个+1

可以把第零行置0 这样第一行也可以按这个方式处理

省的特判

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int a[N][N];

int l[N],r[N],s[N];

int n,m;

int work(int h[]){

    h[0]=h[m+1]=-1;//处理边界情况 最左最右有个高度不可能更小的柱子

    int top=0;

    s[0]=0;

    //求左边最近的小于 左边开始遍历 栈内应为单增 所以出现往下趋势 出栈

    for(int i=1;i<=m;i++){

        while(h[i]<=h[s[top]])

            top--;

        l[i]=s[top];

        s[++top]=i;

    }

    top=0;

    s[0]=m+1;

    //求右边最近的小于 右边开始遍历 栈内应为单增 所以出现往下趋势 出栈

    for(int i=m;i>=1;i--){

        while(h[i]<=h[s[top]])

            top--;

        r[i]=s[top];

        s[++top]=i;

    }

    int res=0;

    for(int i=1;i<=m;i++)

        res=max(res,h[i]*(r[i]-l[i]-1));

    return res;

}

int main()

{

    cin>>n>>m;

    //从1开始 便于处理第一行的1（也等于上一行的0加上1）

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            char c;

            cin>>c;

            if (c=='F')

                a[i][j]=a[i-1][j]+1;

        }

    }

    // for(int i=0;i<=n;i++){

    //     for(int j=0;j<=m;j++){

    //         cout<<a[i][j]<<" ";

    //     }

    //     cout<<endl;

    // }

    int res=0;

    for(int i=1;i<=n;i++){

        res=max(res,work(a[i]));

    }

    cout<<res*3;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[发射站|发射站]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调栈/接雨水|接雨水]]