BOJ14500_테트로미노

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

 

문제요약

1. 그림과 같은 도형을 폴리오미노라고 한다

폴리오미노는 위 5가지만 존재한다

2. 크기가 N M인 종이 위에 폴리오미노를 하나 둔다

3. 폴리오미노에 해당하는 칸에 있는 숫자들의 합이 최대인 합을 출력

4. 폴리오미노는 회전 및 대칭 시켜도 된다

문제issue

딱히 없음

 

해결흐름

1. 총 5가지 폴리오미노를 회전 및 대칭 시켰을 때 모양이 변하는 폴리오미노까지 합하면 총 19가지의 형태가 나온다

2. N X M에서 한 칸당 19가지 형태의 합을 모두 살펴본다

3. 최댓값을 도출한다

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    
    private static int[][] dr = {
            {0,0,0}, {1,2,3}, {0,1,1}, {1,2,2}, {1,2,2},
            {1,1,1}, {1,1,1}, {1,1,2}, {1,1,2}, {0,1,1},
            {0,1,1}, {0,0,1}, {1,1,1}, {1,2,1}, {1,2,1},
            {0,0,1}, {0,0,1}, {0,1,2}, {0,1,2}
            };
    private static int[][] dc = {
            {1,2,3}, {0,0,0}, {1,0,1}, {0,0,1}, {0,0,-1},
            {0,1,2}, {0,-1,-2}, {0,1,1}, {0,-1,-1}, {1,1,2},
            {-1,-1,-2}, {1,2,1}, {-1,0,1}, {0,0,1}, {0,0,-1},
            {1,2,2}, {-1,-2,-2}, {-1,-1,-1}, {1,1,1}
            };
 
    public static void main(String[] args) throws Exception {
        
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // start
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < dr.length; k++) {
                    int sum = 0;
                    sum += map[i][j];
                    for (int l = 0; l < 3; l++) {
                        int nr = i + dr[k][l];
                        int nc = j + dc[k][l];
                        if(nr >= 0 && nr < N && nc >= 0 && nc < M) {
                            sum += map[nr][nc];
                        }
                        else {
                            sum = 0;
                            break;
                        }
                    }
                    if(max < sum)
                        max = sum;
                }
            }
        }
        System.out.println(max);
    } // end of main
} // end of class