結果

問題 No.34 砂漠の行商人
ユーザー diginatudiginatu
提出日時 2014-10-06 00:48:24
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 1,956 bytes
コンパイル時間 649 ms
コンパイル使用メモリ 92,592 KB
実行使用メモリ 4,376 KB
最終ジャッジ日時 2023-09-02 19:01:33
合計ジャッジ時間 2,391 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,372 KB
testcase_01 AC 1 ms
4,368 KB
testcase_02 AC 2 ms
4,372 KB
testcase_03 AC 1 ms
4,368 KB
testcase_04 AC 3 ms
4,372 KB
testcase_05 AC 4 ms
4,372 KB
testcase_06 AC 3 ms
4,368 KB
testcase_07 AC 7 ms
4,372 KB
testcase_08 AC 8 ms
4,372 KB
testcase_09 AC 7 ms
4,368 KB
testcase_10 AC 8 ms
4,372 KB
testcase_11 AC 17 ms
4,372 KB
testcase_12 AC 2 ms
4,372 KB
testcase_13 AC 18 ms
4,372 KB
testcase_14 AC 14 ms
4,372 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 3 ms
4,372 KB
testcase_17 AC 2 ms
4,372 KB
testcase_18 AC 2 ms
4,372 KB
testcase_19 AC 7 ms
4,372 KB
testcase_20 AC 10 ms
4,368 KB
testcase_21 AC 4 ms
4,372 KB
testcase_22 AC 3 ms
4,368 KB
testcase_23 AC 2 ms
4,372 KB
testcase_24 AC 11 ms
4,368 KB
testcase_25 AC 4 ms
4,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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