結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// : (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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0