Official
C - Takahashi Gets Lost Editorial by leaf1415
高橋君が現在いるマスが決まると、その場合の不時着したマスも(存在すれば)一意に定まるので、現在いるマスの代わりに不時着したマスとしてあり得るものを数えることにします。
そのためには、グリッド上のマスそれぞれについて「そのマスが不時着したマスとしてあり得るか」、つまり、「そのマスに不時着したとするとそこから海に入らずに文字列 \(T\) に従う移動ができるか」を実際にシミュレーションによって確かめ、条件を満たすマスの個数をカウントすればよく、本問題はそれをプログラムとして正しく実装できるかを問うています。
\(HW\) 個あるマスそれぞれについて長さ \(N\) の文字列 \(T\) に従ったシミュレーションを行うので、時間計算量は \(O(HWN)\) です。
以下に、C++ 言語による本問題の正解例を記載します。
#include <iostream>
using namespace std;
int h, w, n;
string t, s[505];
int main(void)
{
cin >> h >> w >> n;
cin >> t;
for(int i = 1; i <= h; i++) cin >> s[i];
int ans = 0;
for(int i = 1; i <= h; i++){
for(int j = 0; j < w; j++){
if(s[i][j] == '#') continue;
int I = i, J = j; bool ok = true;
for(auto c : t){
if(c == 'L') J--;
if(c == 'R') J++;
if(c == 'U') I--;
if(c == 'D') I++;
if(s[I][J] == '#'){
ok = false;
break;
}
}
if(ok) ans++;
}
}
cout << ans << endl;
return 0;
}
posted:
last update: