[白俊]#16988 Baaaaaaduk 2(Easy)

質問する

西暦2116年、人類はAIのライバルではなくなった.筋肉、爆発力、創造力、思考力、問題解決能力、さらには人間味さえもAIは人間より強い.AIは地球全体を管理し、人類はすでに地球の主人の位から追い出された.幸いなことに、AIは人間を敵視するのではなく、AIが蓄積した輝かしい技術の発展に伴い、誰もが無制限の火災を使って、1世紀前に人々が望んでいた金持ちの無職の遊民のような生活を楽しむことができるようになった.多くの人類は現状に満足し、発展をあきらめずに遊びながら時間をつぶしているが、一部の人類は人類の栄光を回復するために抵抗軍を組織してAIと戦っている.
抵抗軍はAIの勝算のある種目を探している.これらの種目でAIと勝負し、挑戦精神と人類の偉大さを全人類に証明したいからだ.抵抗軍指導部は12時間もかけて会議を開き、AIのために勝算のあるプロジェクトを探した.会議ではアルゴリズム解題対決、石切り布総稲妻悪魔用水空気スポンジ狼人蛇ゲーム、CatchMind、チェス、星間争覇、隠便ゲーム、イチゴ2位、イチゴスイカニンジンメロンメロンゲーム、百日場、写生大会など多くの創意があったが、0.01%の項目だけが勝算がないように見えた.
こうして、みんなががっかりしている間に、歴史の本をめくって、人類がAIに勝算のあるプロジェクトを見つけた人がいました.100年前の李セソクとアルファ高校の囲碁対決だ.もちろん、アルファゴはそれ以来発展し続け、囲碁では勝算はないものの、囲碁のルールを変えたBaduk 2種目では、この3つの石がアルファゴに勝ったように、人間はAIに勝算があると考えている.
Baduk 2のルールは囲碁とあまり差がありませんが、二人の選手は交代で石を1つ置くのではなく、石を2つ置くのが違います.便宜上,上下左右に隣接する同一色石の集合をグループと呼ぶ.次のレイアウトでは、黒組と白組がそれぞれ3つ存在します.

Baduk 2では、普通の囲碁のように、自分の石で相手の組み合わせをぎゅっと囲むことで、閉じ込められた石を殺すことができます.あるグループが包囲されているのは、そのグループ内にスペースに隣接する石がないことに等しい.

また、Baduk 2では、すべての空の格子に石を置くことができます.相手の石に囲まれて自分が捕まる場所でも大丈夫です.以下の状況を考えてみましょう.

2つの赤い格子が白衣の立場から手に入ると、つながっている組が黒石に囲まれ、元の囲碁のルールでは白衣の立場から自分が掴んだ場所ですが、BADUK 2ではそれに関係なく2つの白赤の格子から手を取り、8つの黒石の組の石を殺すことができます.
抵抗軍はAIに挑戦状Baduk 2を発行し、AIは意外にもおとなしく挑戦を受けた.現在、抵抗軍は2116年3月9日、人間のプライドを賭けてBaduk 2対決を展開する.そして、あなたが人類の勝利を勝ち取るのを助けるために、あなたの任務はプログラムを編纂して、あなたに今の板の上で2つの石を置いて、できるだけ多く相手の石を殺すことです.人間の名誉を賭けて、現在のバージョンで与えられたときに、2つの石で殺すことができる最大相対石数を求めるプログラムを作成します.

入力

1行目では、碁盤の行数と列数を表すN(3≦N≦20)とM(3≦M≦20)が1つのスペースを隔てている.次のN行では、各行の間にスペースがあり、M個の整数は配列の各行を表します.各セルの値は0、1、2です.0はスペース、1は私の石、2は相手の石を表します.2つ以上のスペースと現在のボード上の2人のプレイヤーが相手の石で厳密に囲まれていない組み合わせを保証することができます.

しゅつりょく

1行目では、現在のパネルに2つの石を配置して殺すことができる相対石の最大数を出力します.

入力例1

3 4
2 0 0 0
0 0 0 0
0 0 0 2

サンプル出力1

1

入力例2

5 4
0 0 0 0
0 2 2 0
0 2 0 0
2 2 0 0
2 2 0 0

サンプル出力2

0

入力例3

8 4
0 0 2 0
0 1 2 2
0 0 1 1
2 0 0 0
0 1 0 0
2 0 1 0
2 0 0 0
0 0 0 0

サンプル出力3

3

入力例4

3 3
2 2 2
2 2 2
0 2 0

サンプル出力4

7

入力例5

8 6
0 0 1 2 2 2
0 0 1 2 2 2
0 1 1 0 2 2
1 2 2 0 1 1
1 2 2 1 0 0
1 2 1 0 2 0
1 1 0 0 0 1
0 1 0 0 0 0

サンプル出力5

13

入力例6

7 7
0 0 0 0 1 0 0
2 0 1 1 2 1 0
2 1 2 0 2 2 1
2 1 2 2 0 1 0
2 1 2 1 0 0 0
2 1 2 1 0 0 0
2 2 1 0 0 0 0

サンプル出力6

8

入力例7

7 5
0 0 1 1 1
0 1 2 2 2
2 1 2 1 1
2 1 2 0 2
0 1 2 0 1
0 1 2 2 2
0 0 1 1 1

サンプル出力7

10

に答える

この問題はdfs(深さ優先探索)アルゴリズムの組合せとbfs(幅優先探索)を用いた死石数検査によって解決できる.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static boolean[][] visited;
    static int N;
    static int M;
    static int ans = 0;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0,- 1, 1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        int[][] board = new int[N][M];

        for(int i=0; i<N; i++) {
            input = br.readLine().split(" ");
            for(int j=0; j<M; j++)
                board[i][j] = Integer.parseInt(input[j]);
        }

        dfs(board,0, 0, 0);

        System.out.println(ans);
    }

    public static void dfs(int[][] board, int row, int col, int cnt) {
        if(cnt==2) {
            visited = new boolean[N][M];
            int total = 0;

            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(!visited[i][j] && board[i][j]==2)
                        total+=bfs(board, i, j);
                }
            }
            ans = Math.max(total, ans);

            return;
        }

        for(int i=row; i<N; i++) {
            int j = 0;
            if(i==row)
                j = col;

            for(; j<M; j++) {
                if(board[i][j]==0) {
                    board[i][j] = 1;
                    dfs(board, i, j, cnt+1);
                    board[i][j] = 0;
                }
            }
        }
    }

    public static int bfs(int[][] board, int x, int y) {
        Queue<Pair> queue = new LinkedList<>();
        visited[x][y] = true;
        queue.add(new Pair(x, y));
        int cnt = 1;
        boolean flag = false;

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();

            for(int i=0; i<4; i++) {
                int nx = temp.x+dx[i];
                int ny = temp.y+dy[i];

                if(nx<0 || nx>=N || ny<0 || ny>=M || visited[nx][ny] || board[nx][ny]==1) continue;

                if(board[nx][ny]==0)
                    flag = true;

                else if(board[nx][ny]==2) {
                    visited[nx][ny] = true;
                    cnt++;
                    queue.add(new Pair(nx, ny));
                }
            }
        }

        if(flag)
            return 0;

        return cnt;
    }

    public static class Pair{
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}