結果

問題 No.34 砂漠の行商人
ユーザー krotonkroton
提出日時 2015-06-15 19:54:55
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 653 ms / 5,000 ms
コード長 983 bytes
コンパイル時間 1,193 ms
コンパイル使用メモリ 148,048 KB
実行使用メモリ 58,024 KB
最終ジャッジ日時 2023-09-10 19:09:12
合計ジャッジ時間 5,000 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 4 ms
7,124 KB
testcase_03 AC 2 ms
5,660 KB
testcase_04 AC 18 ms
14,020 KB
testcase_05 AC 21 ms
17,004 KB
testcase_06 AC 10 ms
11,996 KB
testcase_07 AC 35 ms
25,336 KB
testcase_08 AC 43 ms
29,324 KB
testcase_09 AC 194 ms
32,060 KB
testcase_10 AC 36 ms
23,788 KB
testcase_11 AC 381 ms
53,968 KB
testcase_12 AC 13 ms
10,416 KB
testcase_13 AC 653 ms
58,024 KB
testcase_14 AC 479 ms
51,992 KB
testcase_15 AC 4 ms
4,912 KB
testcase_16 AC 38 ms
15,040 KB
testcase_17 AC 3 ms
5,920 KB
testcase_18 AC 6 ms
7,364 KB
testcase_19 AC 157 ms
37,448 KB
testcase_20 AC 265 ms
44,984 KB
testcase_21 AC 5 ms
6,980 KB
testcase_22 AC 10 ms
9,220 KB
testcase_23 AC 5 ms
6,680 KB
testcase_24 AC 343 ms
47,912 KB
testcase_25 AC 27 ms
14,004 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