結果

問題 No.34 砂漠の行商人
コンテスト
ユーザー diginatu
提出日時 2014-10-06 00:48:24
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 16 ms / 5,000 ms
コード長 1,956 bytes
コンパイル時間 794 ms
コンパイル使用メモリ 104,304 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 01:27:28
合計ジャッジ時間 1,795 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std.stdio, std.string, std.conv
,std.array,std.algorithm, std.range
,std.math;

void main(){
  auto buf = readln().strip().split().map!(to!int)();
  immutable N = buf[0];
  immutable V = buf[1];
  immutable Sx = buf[2];
  immutable Sy = buf[3];
  immutable Gx = buf[4];
  immutable Gy = buf[5];

  int[][] L = new int[][](N);
  int[][] dp = new int[][](N);
  int[][] dp2 = new int[][](N);
  foreach(immutable int i; 0 .. N) {
    dp[i] = new int[](N);
    dp2[i] = new int[](N);
    L[i] = readln().strip().split().map!(to!int)().array;
  }

  dp[Sy-1][Sx-1] = V;

  //writeln();
  //foreach(immutable int i; 0 .. N) {
    //foreach(immutable int j; 0 .. N)
      //write(dp[i][j], " ");
    //writeln;
  //}

  bool ch = true;

  int co = 0;
  while(ch) {
    ++co;
    ch = false;
    swap(dp, dp2);
    foreach(immutable int i; 0 .. N) {
      foreach(immutable int j; 0 .. N) {
        dp[i][j] = dp2[i][j];
        if(i != 0 &&  dp2[i-1][j]>0 ) {
          immutable tn = dp2[i-1][j] - L[i][j];
          if(dp[i][j] < tn) {
            dp[i][j] = tn;
            ch = true;
          }
        }
        if(j != 0 &&  dp2[i][j-1]>0 ) {
          immutable tn = dp2[i][j-1] - L[i][j];
          if(dp[i][j] < tn) {
            dp[i][j] = tn;
            ch = true;
          }
        }
        if(i != N-1 &&  dp2[i+1][j]>0 ) {
          immutable tn = dp2[i+1][j] - L[i][j];
          if(dp[i][j] < tn) {
            dp[i][j] = tn;
            ch = true;
          }
        }
        if(j != N-1 &&  dp2[i][j+1]>0 ) {
          immutable tn = dp2[i][j+1] - L[i][j];
          if(dp[i][j] < tn) {
            dp[i][j] = tn;
            ch = true;
          }
        }
      }
    }

    //writeln();
    //foreach(immutable int i; 0 .. N) {
      //foreach(immutable int j; 0 .. N)
        //write(dp[i][j], " ");
      //writeln;
    //}

    if(dp[Gy-1][Gx-1] > 0) {
      writeln(co);
      return;
    }
  }

  writeln(-1);
  return;

}
0