ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし

AtCoder Regulat Contest #039 C - 幼稚園児高橋君

はじめに

実装方針

  • 解説スライドがわかりやすいかも

www.slideshare.net

  • 格子をノードとしてグラフっぽい感じにする
  • ノードを訪れた場合は、その上下左右のノードをつなげて、すでに訪れたノードはなかったことにする
  • 座標からノードにアクセスできるようにハッシュで管理

実装概要

Koshiクラス

格子をグラフっぽく管理するクラス

class Koshi{
    static HashMap<String, Koshi> map = new HashMap<String, Koshi>();
    
    Koshi up, down, left, right;
    int x, y;
    
    // イニシャライザ
    Koshi(int x, int y){
        this.x = x;
        this.y = y;
        map.put(hash(), this);
    }
    
    /**
    * 上下左右のKoshiのリンク先を変更する
    */
    void reLink(){
        if(left == null) left = get(x-1, y);
        if(right == null) right = get(x+1, y);
        if(up == null) up = get(x, y+1);
        if(down == null) down = get(x, y-1);
        
        left.right = right;
        right.left = left;
        up.down = down;
        down.up = up;
    }
    
    
    String hash(){
        return x + " " + y;
    }
    
    
    String hash(int x, int y){
        return x + " " + y;
    }
    
    
    /**
    * mapからx,yのKoshiを探してくる
    * なかったら新しく作る
    */
    Koshi get(int x, int y){
        // hashにあったらそれを返す
        if(map.containsKey(hash(x, y))){
            return map.get(hash(x, y));
        }
        // なかったらつくる
        return new Koshi(x, y);
    }
}

Mainクラス

リンクにしたがってノードを辿っては、リンクの更新をする、ということを繰り返す

class Main extends MyUtil{
    public static void main(String[] args) throws Exception{
        new Main().solve();
    }
 
    // public static Graph g;
 
    void solve() throws Exception{
        // code here
        int k = readInt();
        char[] s = readLine().toCharArray();
        
        // koshiが今いる格子
        // 最初は原点にいる
        Koshi koshi = new Koshi(0, 0);
        koshi.reLink();
        
        for(int i = 0; i < k; i++){
            switch (s[i]) {
            case 'L':
                koshi = koshi.left;
                break;
            case 'R':
                koshi = koshi.right;
                break;
            case 'U':
                koshi = koshi.up;
                break;
            case 'D':
                koshi = koshi.down;
                break;
            }
            koshi.reLink();
        }
        System.out.println(koshi.x + " "+ koshi.y);
    }
}