結果

問題 No.34 砂漠の行商人
コンテスト
ユーザー nebukuro09
提出日時 2016-11-10 11:03:05
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 1,269 bytes
コンパイル時間 946 ms
コンパイル使用メモリ 118,400 KB
実行使用メモリ 816,640 KB
最終ジャッジ日時 2024-06-12 04:59:27
合計ジャッジ時間 7,943 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 WA * 1 MLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio;
import std.array;
import std.string;
import std.conv;
import std.algorithm;
import std.typecons;
import std.range;
import std.random;
import std.math;
import std.container;

void main() {
  int INF = 10^^5;
  alias Tuple!(int, "depth", int, "row", int, "col", int, "v") node;
  
  auto input = readln.split.map!(to!int);
  int N = input[0];
  int V = input[1];
  int Sr = input[3]-1;
  int Sc = input[2]-1;
  int Gr = input[5]-1;
  int Gc = input[4]-1;
  auto B = iota(N).map!(_ => readln.split.map!(to!int).array).array;

  int[4] dr = [0, 0, 1, -1];
  int[4] dc = [1, -1, 0, 0];
  auto dist = iota(N).map!(_ => iota(N).map!(_ => INF).array).array;
  DList!node queue;
  queue.insert(node(0, Sr, Sc, V));

  while (!queue.empty) {
    auto n = queue.front;
    queue.removeFront;
    if (n.depth > dist[n.row][n.col])
      continue;
    dist[n.row][n.col] = n.depth;

    foreach (i; 0..4) {
      int nr = n.row + dr[i];
      int nc = n.col + dc[i];
      if (nr < 0 || nr >= N || nc < 0 || nc >= N)
        continue;
      if (n.depth+1 > dist[nr][nc])
        continue;
      if (n.v - B[nr][nc] <= 0)
        continue;
      queue.insert(node(n.depth+1, nr, nc, n.v-B[nr][nc]));
    }
  }

  writeln(dist[Gr][Gc] == INF ? -1 : dist[Gr][Gc]);
}
0