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

ycy25 · 2026-03-06 23:07:10 · 题解

思路

用 dfs，每次沿着一个方向一直走，途中记录下经过的地方，最后扫一遍一共有多少个格子被记录了。

代码

#include<cstdio>
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
bool can[1001][1001];
char g[1001][1001];
int n,m;
void dfs(int x,int y,int d)//d表示方向
{
    if(x<1||y<1||x>n||y>m)return;
    if(g[x][y]=='o')return;
    if(!can[x][y])can[x][y]=1;//记录
    dfs(x+dx[d],y+dy[d],d);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)scanf(" %c",&g[i][j]);
    }
    for(int i=1;i<=n;i++)dfs(i,1,0),dfs(i,m,1);
    for(int i=1;i<=m;i++)dfs(1,i,2),dfs(n,i,3);//从边界开始，向一个方向行驶
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)ans+=(can[i][j]==1);
    }
    printf("%d",ans);
    return 0;//好习惯
}