题解：P15642 [ICPC 2022 Tehran R] Parking Party

SXY83296647 · 2026-03-08 20:07:09 · 题解

思路

提供一种贪心的思路。

阅读题目可知：存在一个 n \times m 的停车场，其中存在一些柱子（用字符 \texttt{o} 表示），车辆只能停在非柱子的区域（用字符 \texttt{.} 表示），且停留后会占据一个单元格。同时，车辆仅能从入口沿着其所在的行或列进入，遇到另一辆车或柱子时停下。

我们可以模拟停车过程：
先从左到右遍历每一行，遇到柱子就停止，统计空位数量，并标记为已停车。
再从右到左遍历每一行，同样遇到柱子停止，只统计未被占的空位。
最后再用同样的方式处理每一列（即按照从上到下、从下到上的规律遍历）。
这样就能得到最大停车数。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int main(){
    cin>>n>>m;
    int p[n][m],vis[n][m];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            vis[i][j]=0;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        for(int j=0;j<m;j++){
            if(s[j]=='.') p[i][j]=1;
            else p[i][j]=0;
        }
    }// 用p存储当前单元格是否为空位
    for (int j=0;j<m;j++){
        for (int i=0;i<n;i++){
            if(p[i][j]==0) break;
            if(vis[i][j]==0){
                cnt++;
                vis[i][j]=1;
            }
        }
    }// 按行从左往右
    for (int j=0;j<m;j++){
        for (int i=n-1;i>=0;i--){
            if(p[i][j]==0) break;
            if(vis[i][j]==0){
                cnt++;
                vis[i][j]=1;
            }
        }
    }// 按行从右往左
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if(p[i][j]==0) break;
            if(vis[i][j]==0){
                cnt++;
                vis[i][j]=1;
            }
        }
    }// 按列从上往下
    for (int i=0;i<n;i++){
        for (int j=m-1;j>=0;j--){
            if(p[i][j]==0) break;
            if(vis[i][j]==0){
                cnt++;
                vis[i][j]=1;
            }
        }
    }// 按列从下往上
    cout<<cnt;
    return 0;
}

时间复杂度：O(mn)。