题解：AT_abc398_d [ABC398D] Bonfire

D - Bonfire

题目大意

给定在无限二维平面上的一个焰火位置

(0, 0)

，每个时刻烟雾会按照方向移动，若时刻

t

烟雾不在

(0,0)

，则在

(0,0)

处重新生成烟雾。我们要判断在每个半时刻

(t+0.5)

时，给定坐标

(R, C)

是否存在烟雾。

解题思路

使用一个哈希集合保存已出现过烟雾的坐标。模拟每次风向移动，将当前位置偏移量与目标坐标

(R, C)

比较，通过哈希集合检查是否存在烟雾。

代码

CPP

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;
}

题解：AT_abc398_d [ABC398D] Bonfire

文章操作

D - Bonfire

题目大意

解题思路

相关推荐

评论

题解：AT_abc398_d [ABC398D] Bonfire