結果
問題 | No.1638 Robot Maze |
ユーザー |
![]() |
提出日時 | 2021-08-07 16:17:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 2,092 bytes |
コンパイル時間 | 1,065 ms |
コンパイル使用メモリ | 119,976 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-18 19:31:22 |
合計ジャッジ時間 | 2,518 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <cmath>#include <deque>#include <algorithm>#include <iterator>#include <list>#include <tuple>#include <map>#include <unordered_map>#include <queue>#include <set>#include <unordered_set>#include <stack>#include <string>#include <vector>#include <fstream>#include <iostream>#include <functional>#include <numeric>#include <iomanip>#include <stdio.h>#include <assert.h>#include <cstring>//eolibraries#define lnf 3999999999999999999#define inf 999999999#define fi first#define se second#define pb push_back#define ll long long#define ld long double#define all(c) (c).begin(),(c).end()#define sz(c) (ll)(c).size()#define make_unique(a) sort(all(a)),a.erase(unique(all(a)),a.end())#define pii pair <ll,ll>#define tpii pair<ll,pii>#define rep(i,n) for(ll i = 0 ; i < n ; i++)#define drep(i,n) for(ll i = n-1 ; i >= 0 ; i--)#define crep(i,x,n) for(ll i = x ; i < n ; i++)#define vi vector <ll>#define vec(...) vector<__VA_ARGS__>#define _37ckhvj ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)//eodefineusing namespace std;const ll mxn=12000;const ll di[]={-1,1,0,0};const ll dj[]={0,0,1,-1};int main(){_37ckhvj;ll h,w;cin>>h>>w;vi mvcost(4,0);rep(i,4) cin>>mvcost[i];ll k,_p;cin>>k>>_p;ll xs,ys,xt,yt;cin>>xs>>ys>>xt>>yt;xs--; ys--; xt--; yt--;vec(vec(char)) a(h,vec(char)(w));rep(i,h) rep(j,w) cin>>a[i][j];vec(vec(ll)) dp(h,vi(w,k+1));priority_queue<tpii,vector<tpii>,greater<tpii>> pq;pq.push({0,{xs,ys}});dp[xs][ys]=0;auto ok=[&](ll x,ll y){bool pok=1;if(min(x,y)<0) return pok=0;if(x>=h or y>=w) return pok=0;if(a[x][y]=='#') return pok=0;return pok=1;};while(sz(pq)){tpii top=pq.top();pii p=top.se;pq.pop();rep(i,4){ll nei=p.fi+di[i],nej=p.se+dj[i];if(ok(nei,nej)){ll cost=top.fi+mvcost[i];if(cost>k) continue;if(a[nei][nej]=='@'){cost+=_p;}if(cost>k) continue;if(dp[nei][nej]>cost){dp[nei][nej]=cost;pq.push({cost,{nei,nej}});}}}}cout<<(dp[xt][yt]>k?"No":"Yes")<<"\n";//return 0;}