結果
問題 | No.2064 Smallest Sequence on Grid |
ユーザー |
![]() |
提出日時 | 2022-09-02 21:40:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 463 ms / 3,000 ms |
コード長 | 1,333 bytes |
コンパイル時間 | 2,368 ms |
コンパイル使用メモリ | 206,624 KB |
最終ジャッジ日時 | 2025-02-07 00:59:25 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define ll long longvector<int> dx = {1, 0};vector<int> dy = {0, 1};int main() {ios::sync_with_stdio(0);cin.tie(0);int H, W;cin >> H >> W;vector<string> S(H);for (int i=0;i<H;i++) cin >> S[i];string ans = "";vector<pair<int, int>> vec;vec.push_back(make_pair(0, 0));while (true) {ans += S[vec[0].first][vec[0].second];vector<pair<int, int>> vec_nxt;char c_max = '{';for (auto ele : vec) {for (int i=0;i<2;i++) {int i_nxt = ele.first + dx[i];int j_nxt = ele.second + dy[i];if (!(0 <= i_nxt && i_nxt < H)) continue;if (!(0 <= j_nxt && j_nxt < W)) continue;if (S[i_nxt][j_nxt] < c_max) {vec_nxt.clear();c_max = S[i_nxt][j_nxt];vec_nxt.push_back(make_pair(i_nxt, j_nxt));} else if (S[i_nxt][j_nxt] == c_max) {vec_nxt.push_back(make_pair(i_nxt, j_nxt));}}}vec = vec_nxt;sort(vec.begin(), vec.end());vec.erase(unique(vec.begin(), vec.end()), vec.end());if (vec.size() == 0) break;}cout << ans << "\n";return 0;}