ABC265のC問題 Belt Conveyorを解説します。
問題のポイント1
無限ループに入ってしまう場合がどういう状況か?ということを把握することです。
一度訪れたことのある場所に再度訪れた場合は、無限ループに入っています。
実装としては、初期値がfalseである2次元配列を準備し、訪れた場所はtrueにしておくということを行います。
問題のポイント2
止まるのがいつか?ということを把握することです。
上下左右の一番端からはみ出るような動きをしたときのみ止まります。
入力例
2 3
RDU
LRU
回答例
#include< bits/stdc++.h >
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
int main() {
int h, w;
cin >> h >> w;
vector< string > s(h);
rep(i, h) cin >> s[i]; // ここまで入力の受け取り
vector< vector< bool > > visited(h, vector< bool >(w)); // 高さh、幅wの2次元配列。すでに訪れた場所かどうかを管理
int nowh = 0, noww = 0; // 現在いる位置の管理(縦、横)
while(1) { // 無限ループ開始
visited[nowh][noww] = true;
int nexth = nowh, nextw = noww; // 次に動く位置の管理(縦、横)
if (s[nowh][noww] == 'U') nexth--;
if (s[nowh][noww] == 'D') nexth++;
if (s[nowh][noww] == 'L') nextw--;
if (s[nowh][noww] == 'R') nextw++;
if (nexth < 0 || nexth >= h || nextw < 0 || nextw >= w) { // 高さh、幅wの2次元配列がはみ出る場合
cout << nowh + 1 << " " << noww + 1 << endl; // 0インデックスを1インデックスに修正して出力
return 0;
}
if (visited[nexth][nextw]) { // 次に動く位置がすでに訪れた場所である場合
cout << -1 << endl;
return 0;
}
nowh = nexth; // 現在いる位置を実際に動かす
noww = nextw;
}
return 0;
}
コメント