結果

問題 No.20 砂漠のオアシス
ユーザー たこしたこし
提出日時 2015-06-12 17:57:38
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,355 ms / 5,000 ms
コード長 2,111 bytes
コンパイル時間 787 ms
コンパイル使用メモリ 98,104 KB
実行使用メモリ 321,904 KB
最終ジャッジ日時 2024-10-13 05:12:37
合計ジャッジ時間 5,032 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,524 KB
testcase_01 AC 5 ms
17,960 KB
testcase_02 AC 5 ms
18,040 KB
testcase_03 AC 22 ms
58,380 KB
testcase_04 AC 33 ms
23,424 KB
testcase_05 AC 199 ms
257,152 KB
testcase_06 AC 182 ms
320,096 KB
testcase_07 AC 1,355 ms
321,904 KB
testcase_08 AC 251 ms
320,504 KB
testcase_09 AC 738 ms
321,152 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 21 ms
16,768 KB
testcase_13 AC 26 ms
20,480 KB
testcase_14 AC 90 ms
34,304 KB
testcase_15 AC 52 ms
26,112 KB
testcase_16 AC 164 ms
69,760 KB
testcase_17 AC 93 ms
49,536 KB
testcase_18 AC 143 ms
60,032 KB
testcase_19 AC 149 ms
70,784 KB
testcase_20 AC 12 ms
11,776 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>

#define INF_MIN 100000000
#define INF 1145141919
#define INF_MAX 2147483647
#define LL_MAX 9223372036854775807
#define EPS 1e-10
#define PI acos(-1)
#define LL long long

using namespace std;

#define MAX_N 201
#define MAX_V 1010

typedef pair<int, int> P;

int N, V, Ox, Oy;
int L[MAX_N][MAX_N];
int maze[MAX_N][MAX_N];

int dp[MAX_N][MAX_N][MAX_V][2];

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

string solve(){

  dp[0][0][V][0] = 0;

  queue<P> que;
  queue<P> Vque;

  que.push(P(0, 0));
  Vque.push(P(V, 0));

  while(que.size()){

    P p = que.front();
    P v = Vque.front();

    que.pop();
    Vque.pop();

    int x = p.first, y = p.second;
    int hp = v.first, flag = v.second;

    if(x == N-1 && y == N-1)
      return "YES";

    for(int d = 0; d < 4; d++){
      int nx = x + dx[d];
      int ny = y + dy[d];
      if(0 <= nx && nx < N && 0 <= ny && ny < N){
	int nextHp = hp - maze[ny][nx];
	if(nextHp <= 0)
	  continue;
	if(nx == Ox && ny == Oy && flag == 0){
	  if(dp[ny][nx][nextHp*2][1] > dp[y][x][hp][0] + 1){
	    dp[ny][nx][nextHp*2][1] = dp[y][x][hp][0] + 1;
	    que.push(P(nx, ny));
	    Vque.push(P(nextHp*2, 1));
	  }
	}
	else{
	  if(dp[ny][nx][nextHp][flag] > dp[y][x][hp][flag] + 1){
	    dp[ny][nx][nextHp][flag] = dp[y][x][hp][flag] + 1;
	    que.push(P(nx, ny));
	    Vque.push(P(nextHp, flag));
	  }
	}
      }
    }
    

  }


  return "NO";

}

int main(){

  cin >> N >> V >> Ox >> Oy;
  Ox--;
  Oy--;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      cin >> maze[i][j];
      for(int k = 0; k < MAX_V; k++){
	dp[i][j][k][0] = dp[i][j][k][1] = INF;
      }
    }
  }

  cout << solve() << endl;

  return 0;

}
0