結果

問題 No.20 砂漠のオアシス
ユーザー shotshot
提出日時 2016-05-02 18:37:36
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,758 bytes
コンパイル時間 1,477 ms
コンパイル使用メモリ 165,240 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-13 05:36:50
合計ジャッジ時間 5,556 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 5 ms
5,248 KB
testcase_04 AC 26 ms
5,248 KB
testcase_05 WA -
testcase_06 AC 25 ms
5,248 KB
testcase_07 WA -
testcase_08 AC 191 ms
5,248 KB
testcase_09 AC 840 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 WA -
testcase_12 AC 11 ms
5,248 KB
testcase_13 AC 14 ms
5,248 KB
testcase_14 AC 85 ms
5,248 KB
testcase_15 AC 41 ms
5,248 KB
testcase_16 WA -
testcase_17 AC 66 ms
5,248 KB
testcase_18 AC 143 ms
5,248 KB
testcase_19 AC 130 ms
5,248 KB
testcase_20 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef pair<int,int>P;
typedef pair<P,P>PP;
priority_queue<PP,vector<PP>,greater<PP> >pq;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
  int n,hp,ox,oy;
  int mas[222][222];
  int dics[222][222][2];//３つ目はオアシスを使えるかどうか
  cin >> n >> hp >> ox >> oy;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin >> mas[i][j];
    }
  }
  
  if(ox==0 && oy==0){
    dics[0][0][0]=hp;
    pq.push(PP(P(hp,0),P(0,0)));//左から体力、オアシス不可、ｘ、ｙ座標
  }else{
    dics[0][0][1]=hp;
    pq.push(PP(P(hp,1),P(0,0)));//左から体力、オアシス不可、ｘ、ｙ座標 
  }

  while(!pq.empty()){
    PP now=pq.top();
    pq.pop();
    
    int sa=0,flag=now.F.S;
    for(int i=0;i<4;i++){
      int nx,ny;
      nx=now.S.F + dx[i];
      ny=now.S.S + dy[i];
      if(nx<0 || ny<0 || nx>=n || ny>=n)continue;
      if(dics[now.S.S][now.S.F][flag] - mas[ny][nx] > 0){//体力が尽きずに移動できたら
	sa=dics[now.S.S][now.S.F][flag] - mas[ny][nx];
      }else continue;
      
      /*ダイクストラの要領*/
      if(dics[ny][nx][flag] < sa){//移動前後でそこの場所への最小ルートが変化しそうだったら
	dics[ny][nx][flag] = sa;
	pq.push(PP(P(sa,flag),P(nx,ny)));
      }
      
      /*オアシスに行く権利があり、その場所の体力最小数が今現在の体力を２倍したものより小さい*/
      if(nx==ox && ny==oy && flag==1 && dics[ny][nx][1] < (2*sa)){
	dics[ny][nx][0]=sa*2;
	pq.push(PP(P(2*sa,0),P(nx,ny)));
      }
    }
  }
  
  if(dics[n-1][n-1][0]>0 || dics[n-1][n-1][1]>0){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}
0