結果
問題 |
No.2064 Smallest Sequence on Grid
|
ユーザー |
![]() |
提出日時 | 2022-09-06 15:55:56 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 958 ms / 3,000 ms |
コード長 | 1,507 bytes |
コンパイル時間 | 4,427 ms |
コンパイル使用メモリ | 144,112 KB |
実行使用メモリ | 23,936 KB |
最終ジャッジ日時 | 2024-11-21 17:09:21 |
合計ジャッジ時間 | 12,532 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; struct Node { int y; int x; char ch; Node(int y = -1, int x = -1, char ch = -1) { this->y = y; this->x = x; this->ch = ch; } bool operator>(const Node &n) const { return ch > n.ch; } }; int main() { int H, W; cin >> H >> W; vector<string> S(H); for (int y = 0; y < H; ++y) { cin >> S[y]; } queue<Node> que; que.push(Node(0, 0, S[0][0])); int history[H][W]; memset(history, -1, sizeof(history)); string ans = ""; ans += S[0][0]; bool visited[H][W]; memset(visited, false, sizeof(visited)); for (int i = 0; i < H + W - 2; ++i) { priority_queue <Node, vector<Node>, greater<Node>> pque; while (not que.empty()) { Node node = que.front(); que.pop(); if (node.y + 1 < H) { pque.push(Node(node.y + 1, node.x, S[node.y + 1][node.x])); } if (node.x + 1 < W) { pque.push(Node(node.y, node.x + 1, S[node.y][node.x + 1])); } } char ch = pque.top().ch; ans += ch; while (not pque.empty()) { Node node = pque.top(); pque.pop(); if (node.ch > ch) break; if (visited[node.y][node.x]) continue; visited[node.y][node.x] = true; que.push(node); } } cout << ans << endl; return 0; }