ABC443-E题解

wrz_pussycat296 · 2026-02-01 00:37:15 · 题解

思路

一看这种题，直接动态规划。

我们定义 v_{i,j} 表示是否能到达 (i,j) 这个点，定义数组 u_{i,j} 表示 (i,j) 这个点下面是否都不为墙。

然后转移就很好办了。

如果当前不为墙且 v_{i+1,j-1},v_{i+1,j},v_{i+1,j+1} 里有一个能被到达，v_{i,j} 就能被到达。

如果当前为墙且 u_{i,j}=1 ，同样如果 v_{i+1,j-1},v_{i+1,j},v_{i+1,j+1} 里有一个能被到达，v_{i,j} 就能被到达。

再考虑转移 u，如果 u_{i+1,j}=1 且 u_{i,j} 不为墙或是墙能被打破，u_{i,j}=1。

最后输出就可以了。是不是很简单啊。

代码

#include<bits/stdc++.h>
using namespace std;
int T,N,C;
char S[3005][3005];
bool v[3005][3005],u[3005][3005];
int h,t;
int p[3005];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&C);
        for(int i=1;i<=N;i++){
            scanf("%s",S[i]+1);
            for(int j=1;j<=N;j++)
            u[i][j]=0,v[i][j]=0;
        }
        u[N][C]=v[N][C]=1;
        for(int j=1;j<=N;j++)
        if(S[N][j]=='.')u[N][j]=1;
        for(int i=N-1;i>=1;i--){
            for(int j=1;j<=N;j++){
                if(S[i][j]=='.'){
                    if(v[i+1][j]==1||v[i+1][j+1]==1||v[i+1][j-1]==1){
                        v[i][j]=1;
                    }
                    if(u[i+1][j]==1)u[i][j]=1;
                }
                else{
                    if(u[i+1][j]==1){
                        if(v[i+1][j]==1||v[i+1][j+1]==1||v[i+1][j-1]==1){
                            v[i][j]=1;
                            if(u[i+1][j]==1)u[i][j]=1;
                        }
                    }
                }
                //cout<<i<<' '<<j<<' '<<v[i][j]<<' '<<u[i][j]<<endl;
            }
        }
        for(int j=1;j<=N;j++)
        cout<<v[1][j];
        cout<<endl;
    }
    return 0;
}

AC 记录