관리 메뉴

공부한것들을 정리하는 블로그 입니다.

골5 14500 테트로미노 - 브루트포스 본문

알고리즘/백준 - 문제풀이

골5 14500 테트로미노 - 브루트포스

호 두 2022. 5. 8. 14:31
반응형

https://www.acmicpc.net/problem/14500

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

 

import java.util.*;

public class Main {
    //테트로미노
    static int[][][] BLOCKS_14500 = {
            //19 4 2
            {{0,0}, {0,1}, {0,2}, {0,3}}
            ,{{0,0}, {1,0}, {2,0}, {3,0}}
            ,{{0,0}, {1,0}, {0,1}, {1,1}}
            ,{{0,0}, {0,1}, {0,2}, {1,2}}
            ,{{0,0}, {1,0}, {2,0}, {0,1}}
            ,{{0,0}, {1,0}, {1,1}, {1,2}}
            ,{{2,0}, {0,1}, {1,1}, {2,1}}
            ,{{1,0}, {1,1}, {1,2}, {0,2}}
            ,{{0,0}, {0,1}, {1,1}, {2,1}}
            ,{{0,0}, {1,0}, {0,1}, {0,2}}
            ,{{0,0}, {1,0}, {2,0}, {2,1}}
            ,{{0,0}, {1,0}, {2,0}, {1,1}}
            ,{{1,0}, {0,1}, {1,1}, {1,2}}
            ,{{0,1}, {1,0}, {1,1}, {2,1}}
            ,{{0,0}, {0,1}, {0,2}, {1,1}}
            ,{{0,0}, {0,1}, {1,1}, {1,2}}
            ,{{0,1}, {1,1}, {1,0}, {2,0}}
            ,{{1,0}, {1,1}, {0,1}, {0,2}}
            ,{{0,0}, {1,0}, {1,1}, {2,1}}
    };
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int ans = 0;
        //전체 블록을 지정
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                //4개의 큐브로 이루어진 도형 19개를 확인
                for (int k = 0; k < 19; k++) {
                    boolean ok = true;
                    //큐브의 값
                    int sum = 0;
                    for (int l = 0; l < 4; l++) {
                        //큐브의 x좌표
                        int x = i + BLOCKS_14500[k][l][0];
                        //큐브의 y좌표
                        int y = j + BLOCKS_14500[k][l][1];

                        //큐브 4개의 값을 모두 구한다
                        if (x >= 0 && x < n && y >= 0 && y < m) {
                            //큐브의 값 = a[x][y]
                            sum += a[x][y];
                        } else {
                            ok = false;
                            break;
                        }
                    }

                    if (ok && ans < sum ) ans = sum;
                }

            }
        }
        sc.close();
        System.out.println(ans);
    }
}
반응형
Comments