結果
問題 | No.971 いたずらっ子 |
ユーザー |
|
提出日時 | 2020-01-17 21:55:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 772 ms / 2,000 ms |
コード長 | 1,864 bytes |
コンパイル時間 | 1,327 ms |
コンパイル使用メモリ | 100,520 KB |
実行使用メモリ | 70,528 KB |
最終ジャッジ日時 | 2024-11-07 11:28:59 |
合計ジャッジ時間 | 7,898 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 |
ソースコード
#include<iostream> #include<string> #include<iomanip> #include<cmath> #include<vector> #include<algorithm> #include<queue> using namespace std; #define int long long #define endl "\n" constexpr long long INF = (long long)1e18; constexpr long long MOD = 1'000'000'007; string yn(bool f){return f?"Yes":"No";} string YN(bool f){return f?"YES":"NO";} #define f first #define s second signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(10); int dx[2] = {1,0}; int dy[2] = {0,1}; int H, W; vector<string> a; vector<vector<int>> dis, dis2; priority_queue<pair<pair<int,int>,pair<int,int>>, vector<pair<pair<int,int>,pair<int,int>>>, greater<pair<pair<int,int>,pair<int,int>>>> Q; cin>>H>>W; a.resize(H); dis.resize(H, vector<int>(W, INF)); dis2.resize(H, vector<int>(W, INF)); for(int i = 0; i < H; i++){ cin>>a[i]; } Q.push({{0,0},{0,0}}); dis[0][0] = 0; dis2[0][0] = 0; while(!Q.empty()){ pair<pair<int,int>,pair<int,int>> P = Q.top(); Q.pop(); int d1 = P.first.first, d2 = P.first.second; int y = P.second.first, x = P.second.second; if(dis[y][x] < d1) continue; if(y == H-1 && x == W-1) break; for(int i = 0; i < 2; i++){ int ny = y + dy[i], nx = x + dx[i]; // cout<<"y = "<<y<<" x = "<<x<<endl; // cout<<"ny = "<<ny<<" nx = "<<nx<<endl; if(ny >= H || ny < 0 || nx >= W || nx < 0) continue; int td = 0; if(a[ny][nx] == 'k') { // cout<<"<><> "<<endl; td = d1 + ny + nx + 1; } else { td = d1 + 1; } // cout<<"td = "<<td<<" dis "<<dis[ny][nx]<<endl; if(dis[ny][nx] > td) { dis[ny][nx] = td; Q.push({{td,0},{ny,nx}}); } } // cout<<endl; } // cout<<dis[0][0]<<endl; // cout<<dis[0][1]<<endl; // cout<<dis[1][0]<<endl; // cout<<dis[1][1]<<endl; cout<<dis[H-1][W-1]<<endl; return 0; }