猫でもわかるWebプログラミングと副業

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

トップ > AtCoder Regulat Contest #039 C - 幼稚園児高橋君

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);
    }
}