[伯俊]14500-トロミノ(java)

質問する

ポリオミの黄色の大きさは1×複数の1人の正方形でつながっている図形で、以下の条件を満たす必要があります.

正方形は互いに重ならない.

図形はすべてつながっています.

正方形のエッジの間には接続されているはずです.つまり、必ずしも頂点と重なる必要はありません.

4つの正方形を結ぶポリオミノをトロミノといい、以下の5種類があります.

美しい大きさはN×Mの紙にトロミノを置きます.紙は1×1つの大きさのセルに分けられ、各セルに整数が書かれています.
1つのトロミノを適当な位置に置いて、プログラムを書いて、トロミノを置いた格子に書いた数字の和を最大化します.
トロミノは正方形を置いて正確にセルを含み、回転したり対称にしたりする必要があります.

入力

第1行目は、用紙の長手方向サイズNおよび横方向サイズMを与える.(4 ≤ N, M ≤ 500)
2行目からN行の紙に数字が書いてあります.i 1行目のj個の数字は、上からiの1番目のセル、左からjの1番目のセルに書かれた数字である.入力は1000を超えない自然数を与えます.

しゅつりょく

最初の行では、トロミノが格子に置かれた数字の和の最値を出力します.

入力例

5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

サンプル出力

19

コード#コード#

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int[][] map = new int[501][501];
    static boolean[][] visited = new boolean[501][501];
    static int[] dr = {-1, 0, 0, 1};   // 북,서,동,남
    static int[] dc = {0, -1, 1, 0};
    static int N, M;
    static int ans = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                visited[i][j] = true;
                findOne(i, j, 1, map[i][j]);
                visited[i][j] = false;
            }
        }

        bw.write(ans + "\n");
        br.close();
        bw.flush();
        bw.close();
    }

    public static void findOne(int row, int col, int cnt, int sum) {
        if (cnt == 4) {
            ans = Math.max(ans, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int next_r = row + dr[i];
            int next_c = col + dc[i];

            if (next_r > 0 && next_c > 0 && next_r <= N && next_c <= M) {
                if (!visited[next_r][next_c]) {
                    visited[next_r][next_c] = true;
                    findOne(next_r, next_c, cnt + 1, sum + map[next_r][next_c]);
                    visited[next_r][next_c] = false;

                    if (cnt == 2) { // ㅗ 모양 테트로미노
                        visited[next_r][next_c] = true;
                        findOne(row, col, cnt + 1, sum + map[next_r][next_c]);
                        visited[next_r][next_c] = false;
                    }
                }
            }
        }
    }
}

整理する

알고리즘
1. 이중 for 문안에서 visited를 true로 설정해 주면서 테트로미노의 시작점을 만든다.
2. findOne에서는 북, 서, 동, 남 순서대로 훑으면서 범위를 벗어나지 않으면 테트로미노를 확장시킨다.
3. ㅗ 모양 테트로미노를 만들기 위해서 cnt==2일 때는 따로 처리해 준다.
    - next 값을 true로 설정해 테트로미노를 한 칸 확장만 시키고, 재귀 호출은 현재 값을 파라미터로 넘겨준다.
4. 4칸이 되었을 때 테트로미노의 숫자 합의 최댓값이면 ans를 갱신시킨다.