题解：AT_abc398_d [ABC398D] Bonfire

SunburstFan · 2025-03-23 10:36:09 · 题解

D - Bonfire

题目大意

给定在无限二维平面上的一个焰火位置 (0, 0)，每个时刻烟雾会按照方向移动，若时刻 t 烟雾不在 (0,0)，则在 (0,0) 处重新生成烟雾。我们要判断在每个半时刻 (t+0.5) 时，给定坐标 (R, C) 是否存在烟雾。

解题思路

使用一个哈希集合保存已出现过烟雾的坐标。模拟每次风向移动，将当前位置偏移量与目标坐标 (R, C) 比较，通过哈希集合检查是否存在烟雾。

代码

struct P{
    int r,c;
    bool operator==(const P &o)const{
        return r==o.r&&c==o.c;
    }
};

struct Hash{
    size_t operator()(const P &p)const{
        return (size_t)p.r*13131u^(size_t)p.c;
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,r,c;
    cin>>n>>r>>c;
    string s;
    cin>>s;

    unordered_set<P,Hash> st;
    st.insert({0,0});

    int x=0,y=0;
    string ans;
    ans.resize(n);

    for(int i=0;i<n;i++){
        char d=s[i];
        if(d=='N')x--;
        if(d=='S')x++;
        if(d=='W')y--;
        if(d=='E')y++;

        P t={x-r,y-c};
        if(st.find(t)!=st.end())
            ans[i]='1';
        else
            ans[i]='0';

        P cur={x,y};
        if(st.find(cur)==st.end())
            st.insert(cur);
    }

    cout<<ans<<"\n";
    return 0;
}