题解：AT_abc398_d [ABC398D] Bonfire

_sin_ · 2025-03-23 09:04:54 · 题解

注意到移动烟雾非常的困难，但是移动人和火堆是简单的。

考虑将移动烟雾转换为移动火堆，火堆每移动到一个为止就在那个位置上放置一个烟雾，用哈希表或者 map 处理即可。

代码：

#include<bits/stdc++.h>
#define ll long long
#define mkp(x,y) make_pair(x,y)
using namespace std;

ll read(){
    ll x=0,f=1;char ch=getchar_unlocked();
    while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar_unlocked();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar_unlocked();}
    return f*x;
}

const int N = 2e5+5;
int n,x,y,p=0,q=0;
char s[N],ans[N];
map<pair<int,int>,bool>vis;

int main(){vis[mkp(0,0)]=1;
    n=read();x=read(),y=read();
    scanf("%s",s+1);for(int i=1;i<=n;i++){
        if(s[i]=='N')p++,x++;
        if(s[i]=='S')p--,x--;
        if(s[i]=='W')q++,y++;
        if(s[i]=='E')q--,y--;
        vis[mkp(p,q)]=1;
        ans[i]=vis[mkp(x,y)]?'1':'0';
    }puts(ans+1);
    return 0;
}