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

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

トップ > AOJ 1316: The Sorcerer's Donut

AOJ 1316: The Sorcerer's Donut

はじめに

問題文概訳

あなたのマスターは1日だけ街に出かけていった。 これにより、今日だけは彼に怒られずにすむ、とあなたは非常に気楽だった。 しかし、マスターはあなたに、夕方までにドーナツを作っておくように注文した。 ドーナッツが好きすぎて、マスターは一日に10個のドーナッツを食べる。 こんな気楽な日に何故こんな雑用をしなければならないのか。

しかし、先週、あなたはマスターが使う魔法について立ち聞きした。 そしてそれを試そうと思った。 あなたはキッチンで箒に向かって魔法を唱えた。 閃光が発せられ、箒に手足が生えた。 あなたは箒に、小麦粉をわたして生地をこねさせた。 その早いこと早いこと。

数分後、キッチンのテーブルには大量の生地が積み上げられた。 これは来週一週間分のドーナツを作るのに十分な量だ。 「やめていいぞ」とあなたは言ったが、箒は止まらなかった。 あなたはどうやって魔法を止めるのかわからなかった。 キッチンは数百のドーナツ生地でいっぱいになった。 しかし、箒はまだ生地を作り続けている。 箒を止めなければ、キッチンがドーナツ生地だらけになってしまう。

マスターは魔法についてノートに何か書いていないか、と思い、 あなたはマスターの書斎に行き、魔法の止め方が書いてあるノートを発見した。

しかし、それで終わりではなかった。 ノートに書いてあった魔法は簡単には読めなかった。 魔法を読むにはドーナツ型のプラスチックが必要だった。 かれはドーナツの表面を方眼に分けて（図B.1のように）、 そこに文字を書き込んだ（図B.2のように）。 マスターは意味がわからないようにそこに呪文を隠していた。 しかし、あなたは、その中に呪文が2回以上登場していることを知っていた。 （詳しくは後に述べる） 呪文は必ずしも左から右に書かれているとは限らない。 8方向（上下左右と斜め）のいずれかの方向に書かれている。

呪文は、1回以上出現する最も長い文字列である。 プラスチックの正面には正方形が書かれており、その正方形1つに文字が1つ書かれている。 つまり、文字は正方形の列である。 また、その正方形列は以下の条件を持つ。

  • 1つの正方形列は、同じ正方形を2回使ってはならない （違う正方形列が同じ正方形を使うことはありえる）
  • 開始地点が異なるか、開始地点からの進む方向が異なる場合、異なる正方形列とみなされる。

「回文」はこの条件を満たすので、2つの文字列とみなされることに注意せよ。

ドーナッツに書かれた文字は以下のような行列で与えられる

ABCD
EFGH
IJKL

ドーナツの表面は終わりがないことに注意せよ。上と下はつながっているし、 右と左はつながっている。 そのため、行列の縦や横よりも長い文字列ができることもある。

FGHE
FKDEJCHIBGLA
...

のような文字列も上のドーナツに含まれる文字列である。

条件に合うような呪文を見つけるプログラムを書け

入力

入力はいくつかのデータセットからなる それぞれのデータセットは、スペース区切りのh, wから始まる。 これはドーナツのパターンのサイズである。 続くh行にw文字の文字れつが入力される。 文字列は大文字のA-Zからなる。 3 \leq h \leq 10, 3 \leq w \leq 20 である。

入力の終わりは2つのゼロで表される。

出力

それぞれのデータセットに対して、呪文を出力せよ。 もし、最長の文字列が複数あった場合、辞書順で一番前のものを出力せよ。 スペルは2文字以上であると知られている。 もしスペルが見つからなかった場合、0を出力せよ。

方針

  • h,wが非常に小さいので、全部探索する
  • di = {-1, -1, -1, 0, 0, 1, 1, 1}; ... とするような探索は慣れておきたい
  • スタート地点を決め、8方向に1文字読んだらset突っ込むことを繰り返す
  • 上下左右でループするように %h, %w とするが、インデックスがマイナスの方向に飛び出すときにバグらないよう注意
  • すでにsetに入っていた場合は2回目の出現である
    • このとき、この文字列が最長なら長さと単語を記憶しておく
    • 長さが同じなら辞書順最小のものである。JavaならcompareToが使える
  • すでに訪れたことがあるマスに来たらその方向の探索は終了
  • 単語の長さが2以上でないと呪文と認められないので注意する
  • 文字操作をガンガン行う時は、StringBuffer か StringBuilder を使ったほうが早い
    • 過去に、String で通らず StringBuffer なら通ったという経験をしたことがあるので、Javaを使うなら覚えておいたほうがいい

実装

class Main{
    static HashSet<String> set;
    static int maxLength;
    static String ans;
    static char[][] c;
    static int h, w;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            String[] in = br.readLine().split(" ");
            h = Integer.parseInt(in[0]);
            w = Integer.parseInt(in[1]);
            if(h+w == 0) break;
            
            c = new char[h][w];
            for(int i = 0; i < h; i++)
                c[i] = br.readLine().toCharArray();
            
            set = new HashSet<String>();
            maxLength = 0;
            ans = "0";
            for(int i = 0; i < h; i++){
                for(int j = 0; j < w; j++){
                    // i, j から始まる文字列を調べる
                    check(i, j);
                }
            }
            
            if(maxLength >= 2){
                System.out.println(ans);
            }else{
                System.out.println("0");
            }
        }
    }
    
    static int[] di = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dj = {-1, 0, 1, -1, 1, -1, 0, 1};
    static void check(int i, int j){
        for(int k = 0; k < 8; k++){
            // 方向が決定
            boolean[][] visited = new boolean[h][w];
            int ii = i, jj = j;
            String str = "";
            while(!visited[ii][jj]){
                str += "" + c[ii][jj];
                
                if(set.contains(str)){
                    // すでに出現したことがある場合
                    int str_len = str.length();
                    if(maxLength < str_len){
                        // 長さの記録更新
                        ans = str;
                        maxLength = str_len;
                    }else if(maxLength == str_len && str.compareTo(ans) < 0){
                        // 長さは同じだけど辞書順で早い場合
                        ans = str;
                        maxLength = str_len;
                    }
                }else{
                    set.add(str);
                }
                visited[ii][jj] = true;
                ii = (ii + di[k] + h) % h;
                jj = (jj + dj[k] + w) % w;
            }
        }
    }
}

StringBuffer を使わず String を使った場合