結果
問題 | No.971 いたずらっ子 |
ユーザー |
![]() |
提出日時 | 2020-01-17 21:46:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 698 ms / 2,000 ms |
コード長 | 2,744 bytes |
コンパイル時間 | 2,033 ms |
コンパイル使用メモリ | 201,864 KB |
最終ジャッジ日時 | 2025-01-08 18:23:51 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#pragma target("avx") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll, ll> P; typedef vector<ll> V; typedef unordered_map<ll, ll> U_MAP; typedef priority_queue<ll> pq; typedef priority_queue<ll, vector<ll>, greater<ll>> rpq; const int INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10; const ll LINF = 1e18; #define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++) #define rrep(i, a, b) for (ll i = (a); i < (b); i++) #define rrrep(i, a, b) for (ll i = (a); i >= (b); i--) #define all(v) (v).begin(), (v).end() #define Size(n) (n).size() #define Cout(x) cout << (x) << endl #define doublecout(a) cout << fixed << setprecision(15) << a << endl; #define fi first #define se second #define m_p make_pair #define p_b push_back string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string)s); } string to_string(bool b) { return (b ? "true" : "false"); } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto& x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) //------ Believe yourself as a genius!!!!!! ------ int dy[] = {1, 0}; int dx[] = {0, 1}; // int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1}; string alph("abcdefghijklmnopqrstuvwxyz"); char s[2200][2200]; ll n, cnt, ans, a, b, c, d, tmp, m, h, w, x, y, sum, k, q; ll dat[2200][2200]; int main(void) { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); cin >> h >> w; rep(i, h) rep(j, w) cin >> s[i][j]; priority_queue<pair<ll, P>, vector<pair<ll, P>>, greater<pair<ll, P>>> que; que.push({0, {0, 0}}); rep(i, h) rep(j, w) dat[i][j] = LINF; dat[0][0] = 0; while (1) { if (que.empty()) break; pair<ll, P> X; X = que.top(); que.pop(); int cost = X.fi, y = X.se.fi, x = X.se.se; if (dat[y][x] < sum) continue; rep(i, 2) { int nx = x + dx[i], ny = y + dy[i]; ll now_cost = cost; if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue; now_cost++; if (s[ny][nx] == 'k') { now_cost += (nx + ny); } if (dat[ny][nx] <= now_cost) continue; que.push({now_cost, {ny, nx}}); dat[ny][nx] = now_cost; } } Cout(dat[h - 1][w - 1]); return 0; }