結果
問題 | No.34 砂漠の行商人 |
ユーザー |
|
提出日時 | 2024-10-23 20:39:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,861 bytes |
コンパイル時間 | 4,791 ms |
コンパイル使用メモリ | 285,348 KB |
実行使用メモリ | 785,144 KB |
最終ジャッジ日時 | 2024-10-23 20:40:12 |
合計ジャッジ時間 | 18,434 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | MLE * 26 |
ソースコード
// #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> // #include <atcoder/all> using namespace std; // using namespace atcoder; #define rep(i,m,n,k) for (int i = (int)(m); i < (int)(n); i += (int)(k)) #define rrep(i,m,n,k) for (int i = (int)(m); i > (int)(n); i += (int)(k)) #define all(x) x.begin(),x.end() #define ll long long #define list(T,A,N) vector<T> A(N);for(int i=0;i<(int)(N);i++){cin >> A[i];} template<typename T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;} template<typename T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;} // #define int long long int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int N,V,sx,sy,gx,gy; cin >> N >> V >> sx >> sy >> gx >> gy; vector<vector<int>> L(N,vector<int> (N)); rep(i,0,N,1){ rep(j,0,N,1){ cin >> L[j][i]; } } vector<pair<int,int>> dxy = {{-1,0},{1,0},{0,1},{0,-1}}; vector<int> val(200000000); sx -=1; sy -=1; gx -=1; gy -=1; int N2 = N*N; val[sx+N*sy+N2*V] = 1; queue<int> v; v.push(sx+N*sy+N2*V); while(!v.empty()){ auto xym = v.front(); v.pop(); auto m = xym/N2; auto y = xym%N2/N; auto x = xym%N; for(auto [dx,dy]:dxy){ if((x+dx>=N)||(y+dy>=N)||(x+dx<0)||(y+dy<0)) continue; if(m-L[x+dx][y+dy]<=0) continue; if(val[x+dx+N*(y+dy)+(m-L[x+dx][y+dy])*N2]!=0) continue; if((x+dx==gx)&&(y+dy==gy)){ cout << val[xym] << endl; return 0; } val[x+dx+N*(y+dy)+(m-L[x+dx][y+dy])*N2] = val[xym]+1; v.push(x+dx+N*(y+dy)+(m-L[x+dx][y+dy])*N2); } } cout << -1 << endl; return 0; }