結果
問題 | No.1638 Robot Maze |
ユーザー |
![]() |
提出日時 | 2021-08-06 21:47:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,151 bytes |
コンパイル時間 | 1,176 ms |
コンパイル使用メモリ | 118,480 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-17 01:41:19 |
合計ジャッジ時間 | 2,533 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 WA * 3 |
ソースコード
#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) //eodefine using 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,lnf)); 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(); if(top.fi!=dp[p.fi][p.se]) continue; // cout<<p.fi<<" "<<p.se<<" "<<top.fi<<"\n"; 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(a[nei][nej]=='@'){ cost+=_p; } if(dp[nei][nej]>cost){ dp[nei][nej]=cost; pq.push({cost,{nei,nej}}); } } } } if(dp[xt][yt]>k){ cout<<"No\n"; }else{ cout<<"Yes\n"; } // return 0; }