CF106D 题解

ikunTLE · 2024-10-05 08:19:37 · 题解

题目传送门

思路

本题可以在前缀和的优化下模拟通过。由于每一次只会在直线上走，我们只需要预处理每一行和每一列可以走的路长。在模拟期间，就可以使用前缀和判断其路程中是否全是可以走的。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e3+10,M=1e5+10;
struct node{
    int x,y;
};vector<node>vc;
int n,m,r[N][N],c[N][N],op[M],len[M],
dx[]={0,-1,1,0,0},dy[]={0,0,0,-1,1};
char s[N][N];
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(s[i][j]>='A'&&s[i][j]<='Z')
                vc.push_back({i,j});
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            r[i][j]=r[i][j-1]+(s[i][j]!='#');
            c[i][j]=c[i-1][j]+(s[i][j]!='#');
        }
    int T=read();
    for(int i=1;i<=T;++i){
        char ch[1];
        scanf("%s",ch);
        len[i]=read();
        if(ch[0]=='N')
            op[i]=1;
        else if(ch[0]=='S')
            op[i]=2;
        else if(ch[0]=='W')
            op[i]=3;
        else op[i]=4;
    }
    string ans="";
    for(auto it:vc){
        int bx=it.x,by=it.y;
        int x=it.x,y=it.y;
        bool flag=true;
        for(int i=1;i<=T;++i){
            int xx=x+dx[op[i]]*len[i];
            int yy=y+dy[op[i]]*len[i];
            if(xx<=0||xx>n||yy<=0||yy>m){
                flag=false;
                break;
            }
            int min_x=min(x,xx),min_y=min(y,yy);
            int max_x=max(x,xx),max_y=max(y,yy);
            if(op[i]>=3){
                if(r[max_x][max_y]-r[min_x][min_y-1]!=len[i]+1)
                    flag=false;
            }
            else if(c[max_x][max_y]-c[min_x-1][min_y]!=len[i]+1)
                flag=false;
            if(!flag)
                break;
            x=xx,y=yy;
        }
        if(flag)
            ans+=s[bx][by];
    }
    if(ans.empty())
        cout<<"no solution\n";
    else{
        sort(ans.begin(),ans.end());
        cout<<ans<<"\n";
    }
    return 0;
}