結果
問題 | No.2064 Smallest Sequence on Grid |
ユーザー |
![]() |
提出日時 | 2022-09-02 21:35:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 213 ms / 3,000 ms |
コード長 | 1,646 bytes |
コンパイル時間 | 2,818 ms |
コンパイル使用メモリ | 223,348 KB |
最終ジャッジ日時 | 2025-02-07 00:51:18 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 |
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-function" #include<atcoder/all> #pragma GCC diagnostic pop using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; const int di[] = {1, 0}; const int dj[] = {0, 1}; } int main() { ios::sync_with_stdio(false); cin.tie(0); int h, w; cin >> h >> w; vector<string> s(h); rep(i, h) cin >> s[i]; string ans(1, s[0][0]); vector<P> pos{{0, 0}}; auto idxchk = [&](int i, int j) { return 0 <= i && i < h && 0 <= j && j < w; }; vector<vector<char>> visited(h, vector<char>(w)); rep(_, h - 1 + w - 1) { vector<P> nxt; char mn = 'z' + 1; for(auto [i, j]: pos) { if (visited[i][j]) continue; visited[i][j] = true; rep(k, 2) { int ni = i + di[k], nj = j + dj[k]; if (!idxchk(ni, nj)) continue; if (s[ni][nj] < mn) { mn = s[ni][nj]; nxt.clear(); nxt.emplace_back(ni, nj); } else if (s[ni][nj] == mn) { nxt.emplace_back(ni, nj); } } } ans += mn; swap(pos, nxt); } cout << ans << '\n'; }