AOJ : 0215 - パチモンクリーチャー (Pachimon Creature)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0215&lang=jp
日本語の問題文があるので省略です

アルゴリズム

はじめ、ダイクストラ法で解こうとしましたが、コードを書いている途中、そんなことをしなくても解けることがわかったため、方針を切り替えました。

この問題のポイントは、「ある属性を捕まえるためには、ただ1つだけの属性を使ってしか捕まえられない」ところにあります。
例えば、最初に属性１のモンスターを持っているとすると、その次は、絶対に属性２のモンスターしか捕まえられません。
その次も同様に考えると、属性３のモンスターしか捕まえられません。
つまり、問題文中の属性図のように、はじめに持っているモンスターの属性から、必ず時計回りにモンスターを捕まえていけなければいけないことがわかります。

結果、次のような有向グラフが出来上がります(サンプルの1番目)。

あとは、始点の属性だけ決めて、そこからDPによって五種類の属性を集めるのに最小のコストを求めてやるだけです。

説明下手、お許しください。

プログラム

import java.util.*;
import java.awt.Point;

public class Main{
  private static final int MAX = 9999999;

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    while(true){
      int w = sc.nextInt();
      int h = sc.nextInt();
      if(w == 0 && h == 0) break;

      Point sp = null, gp = null; //スタート,ゴール
      ArrayList<ArrayList<Point>> map = new ArrayList<ArrayList<Point>>(); //属性1~5の場所を記憶したマップ
      for(int i=0;i<5;i++) map.add(new ArrayList<Point>());

      for(int i=0;i<h;i++){
        char[] s = sc.next().toCharArray();
        for(int j=0;j<w;j++){
          if(s[j] == 'S'){
            sp = new Point(j,i);
          }
          else if(s[j] == 'G'){
            gp = new Point(j,i);
          }
          else if(s[j] != '.'){
            map.get(s[j] - '1').add(new Point(j,i));
          }
        }
      }

      int first = -1; //はじめにゲットすべき属性
      int ans = MAX; //最小コスト

      //最初にゲットする属性を決定
      for(int start=0;start<5;start++){
        int[][] dp = new int[5][1000];
        for(int i=0;i<5;i++) Arrays.fill(dp[i],MAX);
        int next = (start + 1) % 5;

        for(int i=0;i<map.get(next).size();i++){
          dp[next][i] = dist(sp,map.get(next).get(i));
        }

        int now = next;
        for(;now!=(start+4)%5;now=(now+1)%5){
          for(int i=0;i<map.get(now).size();i++){
            next = (now + 1) % 5;
            for(int j=0;j<map.get(next).size();j++){
              dp[next][j] = Math.min(dp[next][j], dp[now][i]+dist(map.get(now).get(i),map.get(next).get(j)));
            }
          }
        }

        for(int i=0;i<map.get(now).size();i++){
          int d = dp[now][i] + dist(map.get(now).get(i), gp);
          if(ans > d){
            ans = d;
            first = start;
          }
        }
      }

      if(first == -1) System.out.println("NA");
      else System.out.println((first+1) + " " + ans);
    }
  }

  private static int dist(Point a,Point b){
    return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
  }
}