結果
問題 | No.971 いたずらっ子 |
ユーザー |
![]() |
提出日時 | 2020-01-17 21:43:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,024 ms / 2,000 ms |
コード長 | 1,943 bytes |
コンパイル時間 | 2,102 ms |
コンパイル使用メモリ | 179,924 KB |
実行使用メモリ | 74,084 KB |
最終ジャッジ日時 | 2024-11-07 11:26:14 |
合計ジャッジ時間 | 10,585 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<ll, ll> pll; #define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i)) #define REP(i, n) FOR(i,n,0) #define OF64 std::setprecision(10) const ll MOD = 1000000007; const ll INF = (ll) 1e15; string S[2005]; ll M[2005][2005]; ll T[2005][2005]; ll x[2] = {0, 1}; ll y[2] = {1, 0}; struct Data { pll g; ll c; }; int main() { ll H, W; cin >> H >> W; REP(i, H) { cin >> S[i]; } REP(i, H) { REP(j, W) { M[i][j] = INF; T[i][j] = INF; } } { T[0][0] = 0; queue<Data> q; q.push(Data{pll(0, 0), 0}); while (!q.empty()) { auto t = q.front(); q.pop(); REP(i, 2) { ll nx = x[i] + t.g.first, ny = y[i] + t.g.second; if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue; ll cost = t.c + 1; if (T[nx][ny] <= cost) continue; T[nx][ny] = cost; q.push(Data{pll(nx, ny), cost}); } } } { M[0][0] = 0; priority_queue<Data, vector<Data>, function<bool(Data, Data)>> q([](Data a, Data b) { return a.c > b.c; }); q.push(Data{pll(0, 0), 0}); while (!q.empty()) { auto t = q.top(); q.pop(); REP(i, 2) { ll nx = x[i] + t.g.first, ny = y[i] + t.g.second; if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue; ll cost = t.c + 1; if (S[nx][ny] == 'k') cost += T[nx][ny]; if (M[nx][ny] <= cost) continue; M[nx][ny] = cost; q.push(Data{pll(nx, ny), cost}); } } } cout << M[H - 1][W - 1] << endl; return 0; }