結果
問題 | No.34 砂漠の行商人 |
ユーザー | ayame_py |
提出日時 | 2016-02-09 15:40:23 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,173 bytes |
コンパイル時間 | 1,237 ms |
コンパイル使用メモリ | 160,296 KB |
実行使用メモリ | 73,980 KB |
最終ジャッジ日時 | 2023-10-21 20:34:32 |
合計ジャッジ時間 | 11,194 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge10 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 20 ms
73,312 KB |
testcase_01 | AC | 20 ms
73,312 KB |
testcase_02 | WA | - |
testcase_03 | AC | 21 ms
73,320 KB |
testcase_04 | AC | 30 ms
73,340 KB |
testcase_05 | AC | 31 ms
73,340 KB |
testcase_06 | WA | - |
testcase_07 | AC | 38 ms
73,348 KB |
testcase_08 | AC | 44 ms
73,356 KB |
testcase_09 | AC | 628 ms
73,484 KB |
testcase_10 | AC | 1,234 ms
73,980 KB |
testcase_11 | AC | 508 ms
73,364 KB |
testcase_12 | AC | 31 ms
73,336 KB |
testcase_13 | AC | 1,189 ms
73,616 KB |
testcase_14 | AC | 1,120 ms
73,388 KB |
testcase_15 | AC | 313 ms
73,396 KB |
testcase_16 | AC | 305 ms
73,392 KB |
testcase_17 | AC | 420 ms
73,372 KB |
testcase_18 | AC | 68 ms
73,376 KB |
testcase_19 | AC | 269 ms
73,364 KB |
testcase_20 | AC | 513 ms
73,372 KB |
testcase_21 | AC | 21 ms
73,348 KB |
testcase_22 | AC | 563 ms
73,384 KB |
testcase_23 | AC | 415 ms
73,404 KB |
testcase_24 | AC | 996 ms
73,384 KB |
testcase_25 | AC | 60 ms
73,352 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(ll i=0; i<(ll)(n); i++) #define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++) #define pb push_back #define INF 1000000007 #define all(a) (a).begin(),(a).end() #define per(b) #define MAX_N 100 #define MAX_V 1784 typedef long long ll; typedef pair<int,int> p; int dy[4]={-1,1,0,0}; int dx[4]={0,0,1,-1}; int N,V,Sx,Sy,Gx,Gy; int L[MAX_N][MAX_N]; bool canProceed(int y, int x) {return 0<=x&&x<N&&0<=y&&y<N;} int dp[MAX_N][MAX_N][MAX_V]; int dfs(int y, int x, int v){ if(y==Gy&&x==Gx) return 0; if(dp[y][x][v]!=-1) return dp[y][x][v]; dp[y][x][v]=INF; REP(i,4){ int ny=y+dy[i],nx=x+dx[i]; if(canProceed(ny,nx)){ if(v-L[ny][nx]>0) dp[y][x][v]=min(dp[y][x][v],1+dfs(ny,nx,v-L[ny][nx])); } } return dp[y][x][v]; } int main(){ ios::sync_with_stdio(false); cin >> N >> V >> Sx >> Sy >> Gx >> Gy; V=min(V,MAX_V-1); Sx--;Sy--;Gx--;Gy--; REP(i,N)REP(j,N) cin >> L[i][j]; REP(i,MAX_N)REP(j,MAX_N)REP(k,MAX_V) dp[i][j][k]=-1; int ans=dfs(Sy,Sx,V); if(ans>=INF) cout << -1 << endl; else cout << ans << endl; return 0; }