問題

ざっくり問題日本語訳

上記問題ページの図などを適宜参照してください

あなたの会社の次の製品は、3目並べとは異なる新しい3次元のゲームだ。 2人のプレイヤーは3次元ボードにボールを配置していき、ある長さ以上ボールを連続して並べると勝ちとなるゲームである。

人々はこのゲームを心待ちにしていた。しかし、ゲームの調整がうまくできずにいた。具体的には、ボードのサイズmと、m目並べたら勝ちというmが決まらなかった。このmとnを決めるために、このゲームをシミュレートしたい。

ゲームのルールは以下のとおりである。

2人のプレイヤーは黒と白を持ち、黒が先手である。
n * n 個並んだ垂直な杭がある。それぞれの杭にはn個のボールが刺さる。杭は座標(x,y)で区別できる。(1 <= x,y <= n) 杭に刺さったボールはz座標を持つ。ゲームのはじめには、杭には一切ボールが刺さっていない。
プレイヤーは自分のターンに杭を一つ選び、自分の色のボールをその杭に刺す。ボールは重力に下がって一番下まで落下する。るまり、プレイヤーはボールのx座標とy座標を自由に選択できるが、z座標は選択できない。
ゲームの目的は、ボールをm目並べることである。自分の色のボールをm目並べたプレイヤーは勝利する。例えば、(5, 1, 2), (5, 2, 2), (5, 3, 2) はボールが3目並んでいる状態である。ボールの並び方は、垂直、水平、斜めのいずれかであり、例えば (5, 1, 3), (4, 2, 4), (3, 3, 5) は斜めに3目並んでいる状態である。

このゲームの評価のため、mとnを色々決めてこのゲームを遊んだ。このゲームをプレイしたログが与えられるので、あなたはゲームの勝者を計算して欲しい。

「3次元の空間上に同じ色のボールがm目並ぶ」というゲームの勝利条件に気づきにくいため、ログでは、勝負がついたのにもかかわらずゲームを続けてしまっているものもある。例えば、黒がm目並べたにもかかわらず気づかず、その後白がm目並べた場合でも、勝者は黒である。

このゲームには引き分けもある。すべての杭が埋まり、勝敗が決まらない状態でボールを刺す場所がなくなってしまった場合は引き分けである。ここで、例えば、黒が勝利していたにもかかわらず、気付かずに引き分けまでプレイしてしまうこともあり得るが、この場合は黒の勝ちである。

入力

入力はいくつかのデータを含む。データの最初の行は, n, m, p が空白区切りで与えられる。 2 <= m <= n <= 7 であり、pはログのターン数である。

続くp行には x, y が空白区切りで与えられる。これは、そのターンのプレイヤーがx,yにボールを刺したことを表す。1つの杭に刺したボールの数がnを超えることはない。

すべてのデータの最後は3つの0で与えられる

出力

それぞれのデータについて、引き分けの場合は "Draw" と一行に出力せよ。どちらかが勝利した場合は、勝者と勝利までのターン数を空白区切りで一行に出力せよ。勝者は、黒が勝利した場合は "Black"、白が勝利した場合は "White" と出力せよ。

入出力については問題原文の入出力例を確認してください

方針

この問題では、以下を実装する必要がある

ボールを杭に刺すと重力にしたがって落ちるロジック
ボールを刺した時にその人が勝利したかどうか確認するロジック

幸いこの問題におけるnは7以下と非常に小さい。 1については、愚直な実装でもO(n)。2については、8方向にせいぜいnマス調べればいいのでO(8n)。すべてマスが埋まってもターンは n³ なので、どれだけ愚直にやってもO(n + 8n⁴)でn=7でも余裕である。

あとは、ターンの情報がきっちりp行入力されるけど、ゲームは必ずしもpターンで終わるわけではないので、ちゃんと入力に矛盾がないように、意味のないログを読み込んでやること。

実装

ゲームの状態を管理するクラス

class Board{
    int n,m;
    int[][][] board;
    int[] dx = {
            -1,-1,-1,-1,-1,-1,-1,-1,-1,
            0,0,0,0 /*,0,0,0,0,
           1,1,1,1,1,1,1,1,1*/
    };
    int[] dy = {
            -1,-1,-1,0,0,0,1,1,1,
            -1,-1,-1,0 /*,0,1,1,1,
           -1,-1,-1,0,0,0,1,1,1*/
    };
    int[] dz = {
            -1,0,1,-1,0,1,-1,0,1,
            -1,0,1,-1 /*,1,-1,0,1,
           -1,0,1,-1,0,1,-1,0,1*/
    };
    
    Board(int n, int m){
        this.n = n;
        this.m = m;
        board = new int[n][n][n];
    }
    
    boolean put(int x, int y, int c){
        int z;
        // 棒にボールを刺す
        for(z = 0; z < n; z++){
            if(board[x][y][z] == 0){
                board[x][y][z] = c;
                break;
            }
        }
        // 勝ち負けをチェックする
        for(int i = 0; i < dx.length; i++){
            int cnt = 1;
            try{
                for(int mult = 1; mult <= m; mult++){
                    if(board[x + mult*dx[i]][y + mult*dy[i]][z + mult*dz[i]] == c){
                        cnt++;
                    }else{
                        break;
                    }
                }
            }catch(Exception e){}

            try{
                for(int mult = 1; mult <= m; mult++){
                    if(board[x - mult*dx[i]][y - mult*dy[i]][z - mult*dz[i]] == c){
                        cnt++;
                    }else{
                        break;
                    }
                }
            }catch(Exception e){}
            if(cnt >= m) return true;
        }
        return false;
    }
}

Mainメソッド

class Main extends MyUtil{
    // public static Graph g;
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int p = sc.nextInt();
            if(n == 0 && m == 0 && p == 0) break;
            
            Board b = new Board(n, m);
            int[] x = new int[p];
            int[] y = new int[p];
            for (int i = 0; i < p; i++) {
                x[i] = sc.nextInt() - 1;
                y[i] = sc.nextInt() - 1;
            }

            int turn = 1;
            for(int i = 0; i < p; i++) {
                if(b.put(x[i], y[i], turn)) {
                    if(turn == 1){
                        System.out.println("Black " + (i+1));
                        turn = 0;
                        break;
                    }else{
                        System.out.println("White " + (i+1));
                        turn = 0;
                        break;
                    }
                }
                turn *= -1;
            }
            if(turn != 0){
                System.out.println("Draw");
            }
        }
    }
}