結果

問題 No.34 砂漠の行商人
コンテスト
ユーザー kroton
提出日時 2015-06-15 19:54:55
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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