人材獲得作戦4試験問題に友人と挑戦した

高校時代からの地元の友人roiyaru氏
http://d.hatena.ne.jp/roiyaru/
から、先日下記の問題が送られてきた。
http://okajima.air-nifty.com/b/2010/01/post-abc6.html
3時間で解けない奴はコード書く能力ゼロだとまで喝破されているようなので、
うんうん頭をひねって挑戦することになった。


最短経路問題だな→ダイクストラ法と思っていたのだが、考えてみると
ダイクストラ法ってそういえばなんだっけというレベルであった私はググってみた。
移動可能な各点への距離がもとまっている場合の方法だという感じがした。
地図上の経路にダイクストラ法を適用する方法がよく分からん。


そんなこんなで、アスキーアートのマップを読み込んでCUIに表示だけさせた
ところでタバコ吸いながら総当り方式しか思いつかんなー、でも総当りループの
終了条件は何だ?とか順列組み合わせで総当り件数を求めればいいのか?とか
考えながらタバコをとりあえず吸ってふと冷静になると、そういえば
シミュレーションRPGのマップ移動アルゴリズムでいいんじゃないか、と思った。
その手の本によれば、あれは移動可能範囲の各マスを、移動開始場所からの歩数で埋めて
到着地点から逆にスタート地点にさかのぼることで最短経路を障害物も避けながら
移動できる方法が説明されていたような気がした。その本は手元になく、
なんとなくマップを読み込むコードまで書いてしまった私達は、
議論だけでなく結果も確かめたいという気になり、コードを書いてみた。


処理のフローは大体2段階。
1.マップの全ての移動可能なマスを、スタート地点からの最短歩数で埋める。
2.ゴールに隣接するマスから順に、隣接する4方向のマスの中で最小歩数のマスをたどったらそれが最短距離。


後はそれを実装するだけである。
それがこんなコード。

import java.io.*;   
import java.util.*;   
  
public class Mondai {

    public static void main(String[] args) throws Exception {

        String FILE = "mondai.txt";    //問題マップのファイル名
        int width = 0;                 //迷路の幅
        int length = 0;                //迷路の長さ

        //ファイルをreaderに読み込み
        BufferedReader reader = new BufferedReader(new FileReader(new File(FILE)));

        //読み込んだマップを入れるStringのリストを生成  
        List<String> lineList = new ArrayList<String>();

        //マップを一行ずつ読み込んでStringのリストに追加していく
        String line = null;
        while ((line = reader.readLine()) != null) {   
            lineList.add(line);   
        }

        //読み込み終わったテキスト状態のマップから幅と長さを取得
        width = lineList.get(0).length();   
        length = lineList.size();   
  
        //スタート地点からの距離を管理するdistanceMapをマップと同じサイズで生成
        distanceMap[][] dist = new distanceMap[width][length];

        //仮に空欄は998、壁は999、スタートは0、ゴールは1000としてdistanceMapの中身を埋める
        for (int y = 0; y < length; y++) {   
            for(int x = 0; x < width; x++) {   
                dist[x][y] = new distanceMap();   
                String block = lineList.get(y).substring(x, x + 1);   
                if (" ".equals(block)) {   
                    dist[x][y].distance=998;
                } else if ("*".equals(block)) {   
                    dist[x][y].distance= 999;   
                } else if ("S".equals(block)) {   
                    dist[x][y].distance = 0;   
                } else if ("G".equals(block)) {   
                    dist[x][y].distance = 1000;   
                }   
                dist[x][y].x = x;   
                dist[x][y].y = y;   
            }   
        }

        //歩数で埋め終わったかどうかのフラグ
        boolean notFinished = true;

        //歩数カウント変数
        int steps = 0;

        //マップが歩数で埋め終わるまでループ
	while(notFinished){

            //スタート地点のstep0からスタートし、stepをインクリメントしながらその4方のマスをstep+1歩で埋める
            for(int y = 0; y < length; y++) {
                for(int x = 0; x < width; x++) {
                    if(dist[x][y].distance == steps){
                        if((dist[x-1][y].distance != 999 )&&(dist[x-1][y].distance != 1000)&&(dist[x-1][y].distance > steps + 1)){
                            dist[x-1][y].distance = steps + 1;
                        }
                        if((dist[x+1][y].distance != 999 )&&(dist[x+1][y].distance != 1000)&&(dist[x+1][y].distance > steps + 1)){
                            dist[x+1][y].distance = steps + 1;
                        }
                        if((dist[x][y-1].distance != 999 )&&(dist[x][y-1].distance != 1000)&&(dist[x][y-1].distance > steps + 1)){
                            dist[x][y-1].distance = steps + 1;
                        }
                        if((dist[x][y+1].distance != 999 )&&(dist[x][y+1].distance != 1000)&&(dist[x][y+1].distance > steps + 1)){
                            dist[x][y+1].distance = steps + 1;
                        }
                    }
                }
            }
            steps++;

            //空欄がなくなったかどうかを確認するループ
            notFinished = false;
            for(int y = 0; y < length; y++) {
                for(int x = 0; x < width; x++) {
                    if(dist[x][y].distance == 998){
                        notFinished = true;
                    }
                }
            }
        }

	int min = 999;    //ゴールまでの歩数を入れる変数
	int goalx = 0;    //ゴールの座標を入れる変数
        int goaly = 0;    //ゴールの座標を入れる変数

        //ゴールの座標とゴールまでの歩数を取得する
	for(int y = 0; y<length; y++){
	    for(int x = 0; x<width; x++){
                if(dist[x][y].distance == 1000){
                    if(dist[x-1][y].distance < min){
                        min = dist[x-1][y].distance;
                    }
                    if(dist[x+1][y].distance < min){
                        min = dist[x+1][y].distance;
                    }
                    if(dist[x][y-1].distance < min){
                        min = dist[x][y-1].distance;
                    }
                    if(dist[x][y+1].distance < min){
                        min = dist[x][y+1].distance;
                    }
                 goalx = x;
                 goaly = y;
                 }
            }
        }

        //最短距離の座標を管理するshortestRouteを、ゴールまでの歩数分確保
        shortestRoute[] route = new shortestRoute[min+1];
	for(int i = 0; i<min+1; i++){
            route[i] = new shortestRoute();
        }

        //最短距離の最初の座標はゴールの座標にセット
        route[0].x = goalx;
        route[0].y = goaly;

        //ゴールからスタートし、その周りの最小歩数のマスをたどりながらスタート地点までの座標を
        //最短距離管理用のオブジェクトにセットしていく
	for(int i = 0; i<min; i++){
            String direction = "right";
            int minimumCostAround = dist[route[i].x+1][route[i].y].distance;

            if(minimumCostAround > dist[route[i].x-1][route[i].y].distance){
                direction = "left";
                minimumCostAround = dist[route[i].x-1][route[i].y].distance;
            }
            if(minimumCostAround > dist[route[i].x][route[i].y+1].distance){
                direction = "up";
                minimumCostAround = dist[route[i].x][route[i].y+1].distance;
            }
            if(minimumCostAround > dist[route[i].x][route[i].y-1].distance){
                direction = "down";
                minimumCostAround = dist[route[i].x][route[i].y-1].distance;
            }
            if(direction.equals("right")){
                route[i+1].x = route[i].x + 1;
                route[i+1].y = route[i].y;
            } else if(direction.equals("left")){
                route[i+1].x = route[i].x - 1;
                route[i+1].y = route[i].y;
            } else if(direction.equals("up")){
                route[i+1].x = route[i].x;
                route[i+1].y = route[i].y + 1;
            } else if(direction.equals("down")){
                route[i+1].x = route[i].x;
                route[i+1].y = route[i].y - 1;
            } else {
            }
           
        }

        //最短距離の座標のポイントを距離管理用のオブジェクト上で仮に800にする
        for(int i=0;i < min;i++){
            dist[route[i+1].x][route[i+1].y].distance = 800;
        }

        //999は壁、スタートは0、ゴールは1000、最短ルートは800、それ以外は空欄として結果出力
        for(int n=0 ;n < length;n++){
            for(int i=0;i<width;i++){
                    if(dist[i][n].distance==999){
                        System.out.print("*");
                    }else if(dist[i][n].distance==0){
                        System.out.print("S");
                    }else if(dist[i][n].distance==1000){
                        System.out.print("G");
                    }else if(dist[i][n].distance==800){
                        System.out.print("$");
                    }else{
                        System.out.print(" ");
                    }
            }
            System.out.println("");
        }
    }

    //座標とスタート地点からの最短歩数を管理するクラス
    private static class distanceMap {
	int x;
	int y;
	int distance;
    }
    //最短ルートの座標を管理するクラス
    private static class shortestRoute {
        int x;
        int y;
    }
}


この実行結果は、問題のページで求められている正解図とはコースが微妙に違うけれども
歩数のカウント上は変わらない。
スタート地点からの座標で埋め終わって、ゴールから最短歩数を逆にたどる部分でつまづいて
酒飲んで寝た私に代わってコードを完成させたroiyaru氏を賞賛したい。
他の人たちはダイクストラ法だの幅優先探索だので解いているだろうが、
我々は原始的な方法で一応ちゃんとした答えを出せた。感動的な驚きだった。


試験問題サイト
http://okajima.air-nifty.com/b/2010/01/post-abc6.html
roiyaru氏のブログ
http://d.hatena.ne.jp/roiyaru/


参考:
アルゴリズムの勉強のしかた
http://d.hatena.ne.jp/nowokay/20110922#1316676007
アルゴリズムに始まり、アルゴリズムに終わる
http://d.hatena.ne.jp/JavaBlack/20110923/p1
頻出典型アルゴリズムの演習問題としてよさげなやつ
http://d.hatena.ne.jp/kyuridenamida/20111009/1318087144
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズム tim sort
http://d.hatena.ne.jp/gfx/20111019/1318981818
第二版が出ます!プログラミングコンテストチャレンジブック
http://d.hatena.ne.jp/iwiwi/20120111/1326198766