結果
問題 |
No.971 いたずらっ子
|
ユーザー |
|
提出日時 | 2020-11-17 17:11:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,486 bytes |
コンパイル時間 | 1,166 ms |
コンパイル使用メモリ | 99,560 KB |
実行使用メモリ | 814,652 KB |
最終ジャッジ日時 | 2024-07-23 08:21:56 |
合計ジャッジ時間 | 7,757 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 4 |
other | MLE * 1 -- * 20 |
ソースコード
#include <iostream> #include <string> #include <algorithm> #include <iostream> #include <string> #include <algorithm> #include <vector> #include <iomanip> #include <cmath> #include <stdio.h> #include <queue> #include <deque> #include <cstdio> #include <set> #include <map> #include <bitset> #include <stack> #include <cctype> using namespace std; string s[2020]; long long score[2020][2020] = {}; int main() { int h, w; cin >> h >> w; for (int i = 0; i < h; i++) { cin >> s[i]; for (int j = 0; j < w; j++) { score[i][j] = 1000000000000000007; } } score[0][0] = 0; queue<pair<int,int>> que; long long ans = 1000000000000000007; que.push(make_pair(0, 0)); while (!que.empty()) { pair<int, int> p = que.front(); int x = p.first; int y = p.second; long long z = score[x][y]; if (x != h - 1) { if (s[x + 1][y] == 'k') { que.push(make_pair(x + 1, y)); if (score[x + 1][y] > (z + 1) + x + 1 + y) { score[x + 1][y] = (z + 1) + x + 1 + y; } } else { que.push(make_pair(x + 1, y)); if (score[x + 1][y] > (z + 1)) { score[x + 1][y] = (z + 1); } } } if (y != w - 1) { if (s[x][y + 1] == 'k') { que.push(make_pair(x, y + 1)); if (score[x][y + 1] > (z + 1) + x + y + 1) { score[x][y + 1] = (z + 1) + x + y + 1; } } else { que.push(make_pair(x, y + 1)); if (score[x][y + 1] > (z + 1)) { score[x][y + 1] = (z + 1); } } } que.pop(); } cout << score[h - 1][w - 1] << endl; }