問題概要
デイビスは新しくオフィスにケーブルを引こうと思っている。せっかく新しく引いたケーブルに人が引っかかったりすると台無しなので、なるべく人がまたぐ回数を少なくしたい。入力として、ケーブルの両端の位置と、スタッフの移動パターンが入力されるので、ケーブルをうまく引いた時に、スタッフが何回ケーブルをまたぐかを出力する。オフィスは方眼のようになっており、マスをスタッフが移動し、線上にケーブルを引くものとする。
方針
まず問題文が難しいです。以下のPDFを見て問題の概要を把握しましょう。
大雑把な解答の方針としては、従業員の動きを実際にシミュレートした後に、探索で最適なケーブルの引き方を考えていくという感じです。PDFにも書いてありますが、グラフで考えるとわかりやすいでしょう。下の図を見てください。
これはSample Input 1の例です。青丸が従業員で青矢印が従業員の移動、赤丸がケーブルの両端で赤線がまたぐ回数を最小とする引き方の例です。まず、格子について、格子点をノード、枠をエッジとしてグラフに変形します。そして、エッジには、従業員がそこをまたぐ回数を重みとしてつけてやります。すると以下のようになります。
重みが0のエッジについては数字を省略しています。こうすると、後はスタートからゴールまでダイクストラ法を適用して最短距離を求めるだけとまります。ダイクストラ法については、蟻本を始めとして資料が大量にあるので、そちらを参考にすることをおすすめします。ダイクストラ法や幅優先探索は慣れていないとバグを出しやすい実装です。慣れてない人は簡単な問題で慣らすようにしましょう。*1
あとは、このグラフをどうやってデータとして保持しておくかということです。今回はグラフ自体は単純な形ですので、配列などで持っておくのが楽でしょう。その点僕の実装は少しわかりにくいかもしれませんが、一応軽くだけ解説しておきます。
実装
CoordinateクラスとCCompクラス
class Coordinate{ int x, y; int cost; Coordinate(int x, int y, int cost){ this.x = x; this.y = y; this.cost = cost; } public String toString(){ return "(" + x + ", " + y + ")"; } } /** * 昇順 */ class CComp implements Comparator<Coordinate> { public int compare(Coordinate a, Coordinate b) { return a.cost - b.cost; } }
C++のダイクストラ実装は多数転がってるかもしれませんが、Javaは以外と無いのかもしれません。Javaでダイクストラをするには、ノードを表すクラスと、そのノードの大小比較をするComparatorを定義すると思います。今回は格子という特殊な形なので、このようなCoordinateというクラスを定義しました。x, y は座標、costは、そこまで辿り着くのに必要な距離（今回の場合はまたがれる回数の合計）となります。CCompは、CoordinateのComparatorです。Comparator<クラス> を implements し、中に compare メソッドを実行することで、そのクラスの「比較」というものを定義します。comparateは、返り値が0からaとbは同じ値、負ならbが、正ならaが大きいということになります。これを用いて
PriorityQueue<Coordinate> q = new PriorityQueue<Coordinate>(キューのサイズ, new CComp());
と、プライオリティーキューを定義すると、このキューの中身はCoordinateのコスト昇順でソートされます。んでこれを使ってダイクストラします。
Main関数
従業員のシミュレーションやダイクストラを行っているMain関数は以下のようになっています。
class Main { public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(new InputStreamReader(System.in)); // 1行目 int w = sc.nextInt(); int h = sc.nextInt(); int n = sc.nextInt(); int ww = 2*w+1; int hh = 2*h+1; // 2行目 int start_x = sc.nextInt() * 2; int start_y = sc.nextInt() * 2; int end_x = sc.nextInt() * 2; int end_y = sc.nextInt() * 2; int[][] table = new int[ww][hh]; for(int i = 0; i < n; i++){ // それぞれのスタッフの動き int x = sc.nextInt() * 2 + 1; int y = sc.nextInt() * 2 + 1; int t = sc.nextInt(); char[] seq = sc.next().toCharArray(); int len = seq.length; for(int j = 0; j < len*t; j++){ char c = seq[j%len]; int[] d = getD(c); int next_x = x + d[0] * 2; int next_y = y + d[1] * 2; if(inside(next_x, next_y, ww, hh)){ table[x+d[0]][y+d[1]]++; x = next_x; y = next_y; } } } // 次はケーブルのダイクストラ Coordinate start = new Coordinate(start_x, start_y, 1); PriorityQueue<Coordinate> q = new PriorityQueue<Coordinate>(w*h, new CComp()); q.add(start); table[start.x][start.y] = 1; int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; int ans = 0; while(!q.isEmpty()){ Coordinate curr = q.poll(); if(table[curr.x][curr.y] < curr.cost) continue; if(curr.x == end_x && curr.y == end_y){ ans = curr.cost; break; } for(int k = 0; k < 4; k++){ Coordinate next = new Coordinate(curr.x + dx[k]*2, curr.y + dy[k]*2, curr.cost); if(inside(next.x, next.y, ww, hh)){ next.cost += table[curr.x + dx[k]][curr.y + dy[k]]; if(table[next.x][next.y] == 0L || table[next.x][next.y] > next.cost){ q.add(next); table[next.x][next.y] = next.cost; } } } } // ここまでダイクストラ System.out.println(ans - 1); } static boolean inside(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; } static int[] getD(char c){ int[] ret = new int[2]; switch (c) { case 'U': ret[1] = -1; break; case 'D': ret[1] = 1; break; case 'L': ret[0] = -1; break; case 'R': ret[0] = 1; break; } return ret; } }
まとめ
かなり実装量が多くて、初心者には難しい問題だったと思いますが、ほぼ実装ゲーという気がしたので、これくらいは抵抗なく解けるようになりたいです。Javaので正解者数は異様に少なかったです。関数とかコンポーネントにしっかり分けると、コードが見やすくなってバグを出しづらくなるので、ちゃんと分けていきましょう。
ちなみに、今までAOJ-ICPCというサイトを参考に問題を解いていたのですが、今回の問題で250点までの問題はすべて処理しました。次から300点問題に挑んでいきます。
*1:私もこの問題でかなりバグになやまされました。
