結果
問題 | No.20 砂漠のオアシス |
ユーザー | paruki |
提出日時 | 2016-10-07 23:46:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,134 ms / 5,000 ms |
コード長 | 1,310 bytes |
コンパイル時間 | 1,520 ms |
コンパイル使用メモリ | 168,392 KB |
実行使用メモリ | 82,048 KB |
最終ジャッジ日時 | 2024-10-13 05:40:17 |
合計ジャッジ時間 | 4,681 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<<endl #define smax(x,y) (x)=max((x),(y)) #define smin(x,y) (x)=min((x),(y)) #define MEM(x,y) memset((x),(y),sizeof (x)) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; const int DY[] = {-1,0,1,0}; const int DX[] = {0,1,0,-1}; int N, V, OX, OY, L[200][200]; bool visited[200][200][1001][2], ok = false; void f(int y, int x, int v, int flag){ if(ok)return; visited[y][x][v][flag] = true; if(x == N - 1 && y == N - 1){ ok = true; return; } if(OY == y&&OX == x && !flag){ flag = 1; v *= 2; } rep(i, 4){ int ny = y + DY[i], nx = x + DX[i], nv; if(ny >= 0 && ny < N&&nx >= 0 && nx < N){ nv = v - L[ny][nx]; if(nv > 0 && !visited[ny][nx][nv][flag]){ f(ny, nx, nv, flag); } } } } int main(){ cin >> N >> V >> OX >> OY; --OX; --OY; rep(y, N)rep(x, N)scanf("%d", &L[y][x]); f(0, 0, V, 0); puts(ok ? "YES" : "NO"); }