結果
問題 | No.5006 Hidden Maze |
ユーザー |
![]() |
提出日時 | 2022-06-12 16:22:46 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 2,001 bytes |
コンパイル時間 | 2,301 ms |
実行使用メモリ | 22,844 KB |
スコア | 1,979 |
平均クエリ数 | 981.21 |
最終ジャッジ日時 | 2022-06-12 16:22:58 |
合計ジャッジ時間 | 12,021 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,n) for (int i=0;i<(int)(n);i++)#define all(v) v.begin(),v.end()using ll = long long;using pll = pair<ll, ll>;template<class T> void chmin(T& a, T b) {if (a > b) {a = b;}}template<class T> void chmax(T& a, T b) {if (a < b) {a = b;}}int main() {ll h, w, p;cin >> h >> w >> p;srand((unsigned int)time(NULL));vector<char> addc = { 'L','U','R','D' };vector<vector<ll>> grid(h * w + 1);vector<ll> around = { -1,-h,1,w };for (int i = 1; i <= h * w; i++) {rep(j, 4) {ll p = i + around[j];if (i % h == 1 && j == 0) continue;if (i <= w && j == 1) continue;if (i % h == 0 && j == 2) continue;if (h * w - w < i && j == 3) continue;grid[i].push_back(p);}}map<ll, char> mp;mp[h] = 'D'; mp[1] = 'R'; mp[-1] = 'L'; mp[-h] = 'U';map<char, ll> pd;pd['L'] = -1; pd['U'] = -h; pd['R'] = 1; pd['D'] = h;while (true) {vector<ll> dist(h * w + 1, -1);queue<ll> q;q.push(1);dist[1] = 0;while (!q.empty()) {ll x = q.front();q.pop();for (auto& i : grid[x]) {if (i == -1) continue;if (dist[i] == -1) {dist[i] = dist[x] + 1;q.push(i);}}}string root;vector<ll> rootv;rootv.push_back(h * w);ll dt = dist[h * w];if (dt == -1) {cout << 'D' << endl;ll xx;cin >> xx;if (xx == -1) return 0;continue;}ll dtp = h * w;while (dt != 0) {for (auto& i : grid[dtp]) {if (i == -1) continue;if (dt == dist[i] + 1) {root.push_back(mp[dtp - i]);rootv.push_back(i);dt = dist[i];dtp = i;break;}}}reverse(all(root));reverse(all(rootv));cout << root << endl;ll x = 0;cin >> x;if (x == -1) return 0;for (auto& i : grid[rootv[x]]) {if (i == rootv[x] + pd[root[x]]) {i = -1;break;}}if(x+1!=rootv.size()){for (auto& i : grid[rootv[x+1]]) {if (i == rootv[x]) {i = -1;break;}}}}}