AOJ 2583: JAG-channel

方針

• 問題: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2583

基本的に実装が難しいだけの問題。

ポイントは兄弟ノードの情報を保持しておくことです。兄弟ノードの情報を保持しておくことで、縦向きの線が適切に引けます（兄弟ノードがあったら縦線を引く、なかったら引かない）

実装

• http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1375251
• JavaではStringBufferをうまく使わないとMemory Limit Exceeded となってしいます。Stringの結合ではなくStringBufferをうまく渡していきましょう。

class Main extends MyUtil{
    static int n;
    public static void main(String[] args) throws Exception{
        while(true){
            n = readInt();
            if(n == 0) break;
            ArrayList<Node> list = new ArrayList<Node>();
            for(int i = 0; i < n; i++){
                Node node = new Node(readLine());
                list.add(node);
            }
            
            for(int i = 0; i < n; i++){
                System.out.println(list.get(i));
            }
        }
    }
    
}


class Node{
    static Node prev;
    // nextは兄弟ノード
    Node parent, child, next;
    int depth = 0;
    String name;
    
    public Node(String str){
        int i = 0;
        while(str.charAt(i) =='.')
            i++;
        depth = i;
        name = str.substring(i);
        
        while(prev != null){
            if(prev.depth == depth - 1)
                parent = prev;
            
            if(prev.depth == depth){
                prev.next = this;
                parent = prev.parent;
                break;
            }
            prev = prev.parent;
        }
        prev = this;
    }
    
    @Override
    public String toString(){
        StringBuffer buf = new StringBuffer(name);
        if(depth != 0){
            buf.insert(0, '+');
            if(parent.parent != null){
                parent.appendString(buf);
            }
        }
        return buf.toString();
    }
    
    public void appendString(StringBuffer buf){
        if(parent == null) return;

        if(next != null){
            buf.insert(0, '|');
        }else{
            buf.insert(0, ' ');
        }
        if(parent != null){
            parent.appendString(buf);
        }
    }
}