結果
問題 | No.20 砂漠のオアシス |
ユーザー | なお |
提出日時 | 2014-10-09 22:10:01 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 31 ms / 5,000 ms |
コード長 | 2,202 bytes |
コンパイル時間 | 487 ms |
コンパイル使用メモリ | 61,912 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 04:56:46 |
合計ジャッジ時間 | 1,367 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
// 想定解法: 格子点平面上の最短経路探索(Dijkstra, SPFA, etc.)// これはSPFA// オアシスを通らずに体力値未満のコストで到達できるなら YES// スタート→オアシス→ゴール経路で体力値未満のコストで到達できるなら YES// それ以外ならNO#include <cstdio>#include <iostream>#include <deque>using namespace std;#define REP(i, n) for(int(i)=0;(i)<(n);++(i))const int MAXN = 200;int board[MAXN][MAXN];int cost[MAXN][MAXN];const int INF = 1<<29;int N, V, OX, OY;const int dir[][2] = {{1,0},{0,1},{-1,0},{0,-1}};void solve(int sx, int sy){bool inq[MAXN][MAXN];REP(y,N) REP(x,N){cost[y][x] = INF;inq[y][x] = false;}deque<pair<int,int> > q;q.push_back(make_pair(sx,sy));cost[sy][sx] = 0; inq[sy][sx] = true;while(!q.empty()){int x = q.front().first, y = q.front().second;q.pop_front();int nowcost = cost[y][x];inq[y][x] = false;for(int d = 0; d < 4; d++){int mx = x + dir[d][0];int my = y + dir[d][1];if(mx < 0 || my < 0 || mx >= N || my >= N) continue;int nextcost = nowcost + board[my][mx];if(cost[my][mx] > nextcost){cost[my][mx] = nextcost;if(!inq[my][mx]){q.push_back(make_pair(mx,my));inq[my][mx] = true;}}}}return;}int main(){cin >> N >> V >> OX >> OY;REP(y,N) REP(x,N) cin >> board[y][x];solve(0,0);// 直接目的地に行けるか?if(cost[N-1][N-1] < V){cout << "YES" << endl;return 0;}if(OX && OY){int oc = cost[OY-1][OX-1];// オアシスに行けるか?if(oc < V){solve(OX-1,OY-1);// オアシスから目的地に行けるか?if(cost[N-1][N-1] < (V-oc)*2){cout << "YES" << endl;return 0;}}}cout << "NO" << endl;return 0;}