棉花糖题解

题解:因为所有的棉花糖是同时移动的,所以对于每个时刻i我们只需要知道这些棉花糖上下和左右各自偏移了多少.有了这个信息我们就能确定每个棉花糖在时刻i的位置,所以暴力做法就是对于每个棉花糖都进行判断.但是我们可以反过来想,如果存在棉花糖能走到该位置那么是不是就说明我从该位置出发反着走走到的位置得存在棉花糖,因为移动是双向的.

#include <iostream> 
#include <algorithm>
#include <map> 
#define endl "\n"
using namespace std;
typedef pair<int,int> PII;
map<PII,bool> S;
PII p[100010];
char c[4]={'N','S','W','E'};
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin >> n >> m;
    string str;
    cin >> str;
    str=" "+str;
    for(int i=1;i<=n;i++) cin >> p[i].first >> p[i].second;
    for(int i=1;i<=m;i++){
        int x,y;
        cin >> x >> y;
        S[{x,y}]=true; //把每个棉花糖的位置标记一下
    }
    int x=0,y=0; //x为上下偏移,y为左右偏移
    for(int i=1;i<=n;i++){
        for(int j=0;j<4;j++){ //根据风向改变x,y偏移量
            if(str[i]==c[j]){
                x+=dx[j],y+=dy[j];
            }
        }
        if(S.count({p[i].first-x,p[i].second-y})) cout << "Yes" << endl; //如果反向求得的坐标存在棉花糖那么就说明棉花糖能通过该偏移量能够到达
        else cout << "No" << endl;
    }
    return 0;
}