結果
問題 | No.2064 Smallest Sequence on Grid |
ユーザー |
👑 |
提出日時 | 2022-08-29 20:28:55 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 128 ms / 3,000 ms |
コード長 | 1,045 bytes |
コンパイル時間 | 286 ms |
コンパイル使用メモリ | 31,360 KB |
実行使用メモリ | 45,824 KB |
最終ジャッジ日時 | 2024-11-16 01:37:28 |
合計ジャッジ時間 | 3,787 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 |
ソースコード
#include <stdio.h>int main(){int i, H, W;char S[3001][3001];scanf("%d %d", &H, &W);for (i = 0; i < H; i++) {scanf("%s", S[i]);S[i][W] = 'z' + 2;}for (i = 0; i < W; i++) S[H][i] = 'z' + 2;int j, k, q[2][3001][2], head, tail, cur, prev, flag[3001][3001] = {};char ans[6002], tmp;for (k = 1, cur = 1, prev = 0, ans[0] = S[0][0], q[0][0][0] = 0, q[0][0][1] = 0, tail = 1; k < H + W - 1; k++, cur ^= 1, prev ^= 1) {for (head = tail - 1, tail = 0, tmp = 'z' + 1; head >= 0; head--) {i = q[prev][head][0];j = q[prev][head][1];if (tmp > S[i+1][j]) {tmp = S[i+1][j];tail = 0;}if (tmp == S[i+1][j] && flag[i+1][j] == 0) {flag[i+1][j] = 1;q[cur][tail][0] = i + 1;q[cur][tail++][1] = j;}if (tmp > S[i][j+1]) {tmp = S[i][j+1];tail = 0;}if (tmp == S[i][j+1] && flag[i][j+1] == 0) {flag[i][j+1] = 1;q[cur][tail][0] = i;q[cur][tail++][1] = j + 1;}}ans[k] = tmp;}ans[H+W-1] = 0;printf("%s\n", ans);fflush(stdout);return 0;}