結果
問題 | No.971 いたずらっ子 |
ユーザー | coco18000 |
提出日時 | 2020-01-17 21:43:21 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 949 ms / 2,000 ms |
コード長 | 1,943 bytes |
コンパイル時間 | 1,736 ms |
コンパイル使用メモリ | 176,976 KB |
実行使用メモリ | 73,912 KB |
最終ジャッジ日時 | 2023-08-07 07:51:30 |
合計ジャッジ時間 | 9,982 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 944 ms
73,836 KB |
testcase_01 | AC | 949 ms
73,860 KB |
testcase_02 | AC | 685 ms
70,072 KB |
testcase_03 | AC | 836 ms
73,912 KB |
testcase_04 | AC | 789 ms
72,168 KB |
testcase_05 | AC | 769 ms
73,848 KB |
testcase_06 | AC | 563 ms
64,204 KB |
testcase_07 | AC | 8 ms
8,292 KB |
testcase_08 | AC | 196 ms
39,740 KB |
testcase_09 | AC | 186 ms
37,672 KB |
testcase_10 | AC | 6 ms
5,904 KB |
testcase_11 | AC | 2 ms
5,632 KB |
testcase_12 | AC | 2 ms
5,532 KB |
testcase_13 | AC | 2 ms
5,656 KB |
testcase_14 | AC | 15 ms
63,636 KB |
testcase_15 | AC | 2 ms
5,452 KB |
testcase_16 | AC | 4 ms
14,244 KB |
testcase_17 | AC | 2 ms
5,740 KB |
testcase_18 | AC | 2 ms
5,600 KB |
testcase_19 | AC | 2 ms
5,528 KB |
testcase_20 | AC | 2 ms
5,480 KB |
testcase_21 | AC | 2 ms
5,504 KB |
testcase_22 | AC | 2 ms
5,548 KB |
testcase_23 | AC | 2 ms
5,576 KB |
testcase_24 | AC | 2 ms
5,492 KB |
ソースコード
#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; }