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 |