結果

問題 No.34 砂漠の行商人
ユーザー krotonkroton
提出日時 2015-06-15 19:54:55
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 714 ms / 5,000 ms
コード長 983 bytes
コンパイル時間 1,383 ms
コンパイル使用メモリ 162,648 KB
実行使用メモリ 57,984 KB
最終ジャッジ日時 2024-06-28 10:17:40
合計ジャッジ時間 5,204 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,376 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 4 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 18 ms
12,288 KB
testcase_05 AC 22 ms
15,488 KB
testcase_06 AC 10 ms
10,240 KB
testcase_07 AC 35 ms
23,808 KB
testcase_08 AC 43 ms
28,160 KB
testcase_09 AC 206 ms
31,104 KB
testcase_10 AC 37 ms
23,680 KB
testcase_11 AC 422 ms
54,016 KB
testcase_12 AC 12 ms
8,832 KB
testcase_13 AC 714 ms
57,984 KB
testcase_14 AC 534 ms
51,968 KB
testcase_15 AC 5 ms
5,376 KB
testcase_16 AC 38 ms
13,568 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 7 ms
5,376 KB
testcase_19 AC 166 ms
36,420 KB
testcase_20 AC 280 ms
43,776 KB
testcase_21 AC 6 ms
5,376 KB
testcase_22 AC 11 ms
7,296 KB
testcase_23 AC 5 ms
5,376 KB
testcase_24 AC 364 ms
46,848 KB
testcase_25 AC 27 ms
12,544 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

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

struct State {
  int x, y, v, d;
};

int N, V, Sx, Sy, Gx, Gy;
int in[100][100];

bool used[100][100][10001];
int solve() {
  queue<State> Q;
  Q.push(State{ Sx, Sy, V, 0 });
  used[Sx][Sy][V] = true;
  
  while(!Q.empty()) {
    State s = Q.front(); Q.pop();
    int x = s.x, y = s.y, v = s.v, d = s.d;
    if(x == Gx && y == Gy) {
      return d;
    }
    
    for(int i=0;i<4;i++){
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx < 0 || ny < 0 || nx >= N || ny >= N)continue;
      
      int nv = v - in[nx][ny];
      if(nv > 0 && !used[nx][ny][nv]){
        used[nx][ny][nv] = true;
        Q.push(State{ nx, ny, nv, d + 1 });
      }
    }
  }
  
  return -1;
}

int main() {
  cin >> N >> V >> Sx >> Sy >> Gx >> Gy;

  --Sx; --Sy;
  --Gx; --Gy;

  for(int y=0;y<N;y++)for(int x=0;x<N;x++){
    cin >> in[x][y];
  }
  
  cout << solve() << endl;
  return 0;
}
0