風に合わせて煙を動かすと、時刻を \(t\) 進めるのに時間計算量 \(O(t)\) を要し、全体で \(O(N^2)\) となり実行時間制限に間に合いません。
では、どのようにすれば良いでしょうか？

ここで、全ての煙は風に合わせて同じ動きをすることに注目します。すると、次のことが可能になります。

煙を出現した位置で固定して、風に合わせて焚き火と高橋君を動かすことを考える。

つまり、「煙が風に乗って動く」を考えることと、「焚き火と高橋君が風の逆向きに動く」を考えることとは等価です。

これを実現するには、次の処理をすることになります。

• まず、マス \((0,0)\) に煙を生成する。

• 焚き火の位置 \((0,0)\) 、高橋君の位置 \((R,C)\) から始める。

• 時刻 \(t=1,2,\dots,N\) について次を繰り返す。

  • 焚き火と高橋君を次の規則に従って動かす。
    • \(S_i = \) N なら \((r,c)\) から \((r+1,c)\) に動かす。
    • \(S_i = \) W なら \((r,c)\) から \((r,c+1)\) に動かす。
    • \(S_i = \) S なら \((r,c)\) から \((r-1,c)\) に動かす。
    • \(S_i = \) E なら \((r,c)\) から \((r,c-1)\) に動かす。
  • 現在の焚き火の位置に煙を生成する。
  • この時点で高橋君のいる位置に煙があれば 1 、なければ 0 と解答する。

問題文の元々の処理と上記の処理とでは、煙と焚き火と高橋君の相対的な位置は変わりません。
動かすものの数が \(2\) つになっているので、時間計算量が削減できます。

煙の発生した位置の集合を set などのデータ構造で管理することで、 \(O(N \log N)\) といった時間計算量でこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  int n;
  pi t;
  string s;
  cin >> n >> t.first >> t.second;
  cin >> s;
  pi f={0,0};
  set<pi> st;
  st.insert(f);

  for(auto &nx : s){
    if(nx=='N'){
      t.first++;
      f.first++;
    }
    else if(nx=='W'){
      t.second++;
      f.second++;
    }
    else if(nx=='S'){
      t.first--;
      f.first--;
    }
    else{
      t.second--;
      f.second--;
    }
    
    st.insert(f);
    if(st.find(t)==st.end()){cout << "0";}
    else{cout << "1";}
  }cout << "\n";
  return 0;
}