fork download
copy 
  1. import java.awt.Point;
  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.List;
  5. import java.util.Scanner;
  6. import java.util.regex.Pattern;
  7.  
  8. /*
  9. プログラミングのお題スレ Part13 
  10. //mevius.5ch.net/test/read.cgi/tech/1549160513/316
  11.  
  12. 316 名前：デフォルトの名無しさん[sage] 投稿日：2019/02/22(金) 21:42:16.23 ID:THqrb0iU
  13. お題：
  14. 長方形のフィールドが与えられる。フィールド上では上下左右に移動することができる。
  15. 各マスの数字はそのマスに入るためのコストを表す。
  16. SからGに向かうときの最小コストを求めよ。(SとGのコストは0とする)
  17.  
  18. S5111
  19. 1115G
  20. => 6
  21.  
  22. S1111
  23. 98642
  24. G1111
  25. => 9
  26.  
  27. 13457689768914512071934123457
  28. G4578901258901212890361125312
  29. 37890423076834712378998725463
  30. 16890102569615902061456259893
  31. 34582934765923812893461515232
  32. 57896123896741378915691551697
  33. 89013897456123457162501835479
  34. 21389046013845610034623405686
  35. 8902346203948612341356362342S
  36. => ?
  37. */
  38. class Ideone
  39. {
  40.     public static void main(String[] args)
  41.     {
  42.         try (Scanner in = new Scanner(System.in))
  43.         {
  44.             while (in.hasNextLine())
  45.             {
  46.                 ArrayList<String> data = new ArrayList<>();
  47.                 while (in.hasNextLine())
  48.                 {
  49.                     String line = in.nextLine();
  50.                     if (line.isEmpty()) break;
  51.                     data.add(line);
  52.                 }
  53.  
  54.                 solve(data);
  55.             }
  56.         }
  57.     }
  58.  
  59.     static Pattern FIELD_PATTERN = Pattern.compile("[0-9SG]+");
  60.     static void solve(List<String> data)
  61.     {
  62.         if (data.isEmpty()) throw new IllegalArgumentException("フィールドデータが空です");
  63.         Point start = null, goal = null;
  64.         int width = data.get(0).length();
  65.         int height = data.size();
  66.         int[][] cost = new int[height][width];
  67.         for (int y = 0; y < height; y++)
  68.         {
  69.             String s = data.get(y);
  70.             if (width != s.length())
  71.                 throw new IllegalArgumentException("フィールドが矩形ではありません");
  72.             if (!FIELD_PATTERN.matcher(s).matches())
  73.                 throw new IllegalArgumentException("フィールドデータが不正です: " + s);
  74.  
  75.             for (int x = 0; x < s.length(); x++)
  76.             {
  77.                 char c = s.charAt(x);
  78.                 if (c == 'S')
  79.                 {
  80.                     if (start == null) start = new Point(x, y);
  81.                     else throw new IllegalArgumentException("スタート地点が二つあります");
  82.                 } else if (c == 'G')
  83.                 {
  84.                     if (goal == null) goal = new Point(x, y);
  85.                     else throw new IllegalArgumentException("ゴール地点が二つあります");
  86.                 } else
  87.                 {
  88.                     cost[y][x] = c - '0';
  89.                 }
  90.             }
  91.         }
  92.  
  93.         int[][] score = new int[height][width];
  94.         boolean[][] flag = new boolean[height][width];
  95.         for (int[] is : score)
  96.             Arrays.fill(is, Integer.MAX_VALUE);
  97.         score[start.y][start.x] = 0;
  98.  
  99.         while (true)
  100.         {
  101.             Point next = min(score, flag);
  102.             if (next == null) break;
  103.             flag[next.y][next.x] = true;
  104.             if (next.x > 0)
  105.             {
  106.                 int s = score[next.y][next.x] + cost[next.y][next.x - 1];
  107.                 if (s < score[next.y][next.x - 1]) score[next.y][next.x - 1] = s;
  108.             }
  109.             if (next.x < width - 1)
  110.             {
  111.                 int s = score[next.y][next.x] + cost[next.y][next.x + 1];
  112.                 if (s < score[next.y][next.x + 1]) score[next.y][next.x + 1] = s;
  113.             }
  114.             if (next.y > 0)
  115.             {
  116.                 int s = score[next.y][next.x] + cost[next.y - 1][next.x];
  117.                 if (s < score[next.y - 1][next.x]) score[next.y - 1][next.x] = s;
  118.             }
  119.             if (next.y < height - 1)
  120.             {
  121.                 int s = score[next.y][next.x] + cost[next.y + 1][next.x];
  122.                 if (s < score[next.y + 1][next.x]) score[next.y + 1][next.x] = s;
  123.             }
  124.         }
  125.  
  126.         System.out.println("=>" + score[goal.y][goal.x]);
  127.         System.out.println();
  128.     }
  129.  
  130.     // キュー作るの面倒だったので全箇所から最小スコア部分を調べるｗ
  131.     static Point min(int[][] score, boolean[][] flag)
  132.     {
  133.         int h = score.length;
  134.         int w = score[0].length;
  135.         int min = Integer.MAX_VALUE;
  136.         Point point = null;
  137.         for (int y = 0; y < h; y++)
  138.         {
  139.             for (int x = 0; x < w; x++)
  140.             {
  141.                 if (flag[y][x]) continue;
  142.                 if (min > score[y][x])
  143.                 {
  144.                     min = score[y][x];
  145.                     point = new Point(x, y);
  146.                 }
  147.             }
  148.         }
  149.         return point;
  150.     }
  151. }
  152.  
Success #stdin #stdout 0.08s 2184192KB
comments (?)
stdin
copy 
S5111
1115G

S1111
98642
G1111

13457689768914512071934123457
G4578901258901212890361125312
37890423076834712378998725463
16890102569615902061456259893
34582934765923812893461515232
57896123896741378915691551697
89013897456123457162501835479
21389046013845610034623405686
8902346203948612341356362342S
stdout
copy 
=>6

=>9

=>100
https://ideone.com/ZhJHKg
お題スレ13の316
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!