結果
問題 | No.34 砂漠の行商人 |
ユーザー |
|
提出日時 | 2024-10-23 20:39:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,861 bytes |
コンパイル時間 | 4,256 ms |
コンパイル使用メモリ | 285,104 KB |
実行使用メモリ | 394,348 KB |
最終ジャッジ日時 | 2024-10-23 20:39:39 |
合計ジャッジ時間 | 17,005 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 RE * 1 |
ソースコード
// #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 longint 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(100000000);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;}