import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Map.Entry;

import java.util.StringTokenizer;


class Block {


HashMap<Integer, int[][]> shapeList;

int[][] origin;

int[] flag;

ArrayList<Integer> fList;


// 블록에 해당하는 모양 Data를 만들어줍니다.

public Block(int[][] data, int[] flag) {

this.origin = data;

this.flag = flag;


fList = new ArrayList<>();

for (int item : flag) {

fList.add(item);

}


shapeList = new HashMap<>();

createShape();

// printAllShape();

}


// 회전과 대칭에 따른 데이터(모양) 생성

private void createShape() {


int[][] temp = origin;


// 0번 모양

shapeList.put(0, origin);


// 1~3번 모양(90, 180, 270)

for (int i = 1; i <= 3; i++) {

temp = rotate(temp);

if (fList.contains(i)) {

shapeList.put(i, temp);

}

}


// 4번 모양

int[][] rev = null;

if (fList.contains(4)) {

rev = reverse(origin);

shapeList.put(4, rev);

}


temp = rev;

// 5~7번 모양 rev + (90, 180, 270)

if (fList.contains(5)) {

for (int i = 4; i <= 7; i++) {

temp = rotate(temp);

shapeList.put(i, temp);

}

}


}


// 디버깅을 위한 출력

public void printAllShape() {


int[][] shape;

int ysize, xsize;

for (Entry<Integer, int[][]> entry : shapeList.entrySet()) {


shape = entry.getValue();

ysize = shape.length;

xsize = shape[0].length;


Main.log("[%d]", entry.getKey());


for (int i = 0; i < ysize; i++) {

String line = "";

for (int j = 0; j < xsize; j++) {

line += String.format("%d ", shape[i][j]);

}

Main.log(line);

}

}


}


// 회전 유틸

private int[][] rotate(int[][] data) {

int ysize = data.length;

int xsize = data[0].length;

int end_index = ysize - 1;


int[][] rData = new int[xsize][];

for (int i = 0; i < xsize; i++) {

rData[i] = new int[ysize];

for (int j = 0; j < ysize; j++) {

rData[i][j] = data[end_index - j][i];

}

}


return rData;

}


// 대칭 유틸

private int[][] reverse(int[][] data) {

int ysize = data.length;

int xsize = data[0].length;

int end_index = xsize - 1;


int[][] rData = new int[ysize][];

for (int i = 0; i < ysize; i++) {

rData[i] = new int[xsize];

for (int j = 0; j < xsize; j++) {

rData[i][j] = data[i][end_index - j];

}

}


return rData;

}


}


public class Main {


private static int MapSize_Y;

private static int MapSize_X;

static int[][] Map;


static private ArrayList<Block> bList;


private static boolean Debug = true;

private static int MaxSum;


public static void main(String[] args) throws Exception {


BufferedReader br;


if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "2048.txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}

StringTokenizer st;


// 맵 크기

st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());


// 맵 데이터 입력

Map = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

st = new StringTokenizer(br.readLine());

Map[i] = new int[MapSize_X];

for (int j = 0; j < MapSize_X; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

}

}


// 블록을 담을 리스트

bList = new ArrayList<>();

Block item; // 블록에는 모양 값들이 저장 된다.


// 블록 모양, 필요한 모양 값 (0: 원형, 1~3: 회전, 4: 대칭, 5~7: 대칭 후 회전)

int[][] 네모Shape = { { 1, 1 }, { 1, 1 } };

item = new Block(네모Shape, new int[] { 0 });

bList.add(item);


int[][] 일자Shape = { { 1, 1, 1, 1 } };

item = new Block(일자Shape, new int[] { 0, 1 });

bList.add(item);


int[][] 산Shape = { { 1, 1, 1 }, { 0, 1, 0 } };

item = new Block(산Shape, new int[] { 0, 1, 2, 3 });

bList.add(item);


int[][] 기역Shape = { { 1, 0 }, { 1, 0 }, { 1, 1 } };

item = new Block(기역Shape, new int[] { 0, 1, 2, 3, 4, 5, 6, 7 });

bList.add(item);


int[][] 어긋Shape = { { 1, 0 }, { 1, 1 }, { 0, 1 } };

item = new Block(어긋Shape, new int[] { 0, 1, 2, 3, 4, 5, 6, 7 });

bList.add(item);


// 완전탐색

MaxSum = -1;

dfs();


// 시간 출력

System.out.println(MaxSum);

}


public static void dfs() {


int blockLen = bList.size();

// 모든 블록에 대한 경우

for (int i = 0; i < blockLen; i++) {

Block block = bList.get(i);


// 각 블록에 따른 데이터를 가져온다. (대칭 및 회전이 포함된 데이터)

for (Entry<Integer, int[][]> item : block.shapeList.entrySet()) {

int[][] data = item.getValue();

int ysize = data.length, xsize = data[0].length;


// 탐색범위 지정(드레그)

int endy, endx;

endy = MapSize_Y - ysize;

endx = MapSize_X - xsize;


// 지정된 탐색 범위에서, data에 맞도록 검색

search(endy, endx, data);

}


}


}


// 해당 블록 모양을 가지고, 해당 위치에서 검색을 해봅니다.

public static void search(int endy, int endx, int[][] data) {


// 탐색 사이즈

int yszie = data.length, xsize = data[0].length;

// 탐색 구간은 (0,0) ~ (endy, endx) 드레그

for (int y = 0; y <= endy; y++) {

for (int x = 0; x <= endx; x++) {


// Block 모양에 따른 탐색

int sum = 0;

for (int i = 0; i < yszie; i++) {

for (int j = 0; j < xsize; j++) {

if (data[i][j] == 1) { // 탐색

sum += Map[y + i][x + j];

}

}

}


// 최대값 판별

if (MaxSum < sum) {

MaxSum = sum;

}


}

}

// log("합: " + sum);

}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}



'Knowledge > 알고리즘' 카테고리의 다른 글

1767. [SW Test 샘플문제] 프로세서 연결하기  (0) 2017.10.21
백준 3671번: 산업 스파이의 편지  (0) 2017.10.20
백준 13460번: 째로탈출2  (0) 2017.10.20
백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 3190번: 뱀  (0) 2017.10.19

+ Recent posts