結果
問題 |
No.2064 Smallest Sequence on Grid
|
ユーザー |
![]() |
提出日時 | 2023-09-11 06:54:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,300 bytes |
コンパイル時間 | 867 ms |
コンパイル使用メモリ | 84,416 KB |
実行使用メモリ | 817,344 KB |
最終ジャッジ日時 | 2024-06-28 21:05:07 |
合計ジャッジ時間 | 4,703 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 9 MLE * 1 -- * 19 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; using P = pair<int, int>; int main(){ int h, w; cin >> h >> w; vector<string> s(h); for(auto &it: s) cin >> it; vector<vector<vector<P>>> cnt(h+w, vector<vector<P>>(26)); cnt[0][s[0][0]-'a'].emplace_back(0, 0); vector<vector<P>> pre(h, vector<P>(w, {-1, -1})); for(int phase = 0; phase < h+w-1; phase++){ for(int x = 0; x < 26; x++){ if(cnt[phase][x].size() == 0) continue; for(auto &it: cnt[phase][x]){ int i = it.first, j = it.second; // cerr << i << " " << j << ", "; if(i+1 < h){ cnt[phase+1][s[i+1][j]-'a'].emplace_back(i+1, j); pre[i+1][j] = {i, j}; } if(j+1 < w){ cnt[phase+1][s[i][j+1]-'a'].emplace_back(i, j+1); pre[i][j+1] = {i, j}; } } // cerr << endl; break; } } string ans = ""; P cur = {h-1, w-1}; while(cur != P{-1, -1}){ ans += s[cur.first][cur.second]; cur = pre[cur.first][cur.second]; } reverse(ans.begin(), ans.end()); cout << ans << endl; return 0; }