반응형
https://www.acmicpc.net/problem/12100
12100번: 2048 (Easy)
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
www.acmicpc.net
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class B12100 {
static int N;
public static int MaxValue = -987654321;
public static int[] dy = { 0, 0, -1, 1 };
public static int[] dx = { 1, -1, 0, 0 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
int[][] map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int d = 0; d < 4; d++)
DFS(1, d, map);
System.out.println(MaxValue);
}
public static void DFS(int cnt, int d, int[][] map) {
// 깊은복사
int[][] mymap = new int[N][N];
boolean[][] check = new boolean[N][N];
// d 로이동 우 좌 위 아래
for (int i = 0; i < N; i++) {
System.arraycopy(map[i], 0, mymap[i], 0, map[i].length);
}
if (d == 0) {// 우
for (int j = N - 2; j >= 0; j--) {
for (int i = 0; i < N; i++) {
if(map[i][j] == 0) continue;
// seq는 이동할 위치
int seq = j;
while (true) {
seq++;
if (seq >= N) {
seq--;
break;
}
if (mymap[i][seq] == 0)
continue;
if (mymap[i][seq] == mymap[i][j]) {
if (check[i][seq]) {
seq--;
}
break;
} else {
seq--;
break;
}
}
if (j != seq) {
if (mymap[i][j] == mymap[i][seq]) {
check[i][seq] = true;
}
mymap[i][seq] +=mymap[i][j];
mymap[i][j] = 0;
check[i][j] = false;
}
}
}
} else if (d == 1) {// 좌
for (int j = 1; j < N; j++) {
for (int i = 0; i < N; i++) {
if(map[i][j] == 0) continue;
// seq는 이동할 위치
int seq = j;
while (true) {
seq--;
if (seq < 0) {
seq++;
break;
}
if (mymap[i][seq] == 0)
continue;
if (mymap[i][seq] == mymap[i][j]) {
if (check[i][seq]) {
seq++;
}
break;
} else {
seq++;
break;
}
}
if (j != seq) {
if (mymap[i][j] == mymap[i][seq]) {
check[i][seq] = true;
}
mymap[i][seq] +=mymap[i][j];
mymap[i][j] = 0;
check[i][j] = false;
}
}
}
} else if (d == 2) {// 위
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
if(map[i][j] == 0) continue;
// seq는 이동할 위치
int seq = i;
while (true) {
seq--;
if (seq < 0) {
seq++;
break;
}
if (mymap[seq][j] == 0)
continue;
if (mymap[seq][j] == mymap[i][j]) {
if (check[seq][j]) {
seq++;
}
break;
} else {
seq++;
break;
}
}
if (i != seq) {
if (mymap[i][j] == mymap[seq][j]) {
check[seq][j] = true;
}
mymap[seq][j] +=mymap[i][j];
mymap[i][j] = 0;
check[i][j] = false;
}
}
}
} else if (d == 3) {// 아래
for (int i = N - 2; i >= 0; i--) {
for (int j = 0; j < N; j++) {
if(map[i][j] == 0) continue;
// seq는 이동할 위치
int seq = i;
while (true) {
seq++;
if (seq >= N) {
seq--;
break;
}
if (mymap[seq][j] == 0)
continue;
if (mymap[seq][j] == mymap[i][j]) {
if (check[seq][j]) {
seq--;
}
break;
} else {
seq--;
break;
}
}
if (i != seq) {
if (mymap[i][j] == mymap[seq][j]) {
check[seq][j] = true;
}
mymap[seq][j] +=mymap[i][j];
mymap[i][j] = 0;
check[i][j] = false;
}
}
}
}
// if (cnt == 1) {
//
// System.out.println();
//
// for (int i = 0; i < N; i++) {
//
// for (int j = 0; j < N; j++) {
//
// System.out.print(mymap[i][j] + " ");
//
// }
//
// System.out.println();
//
// }
//
// }
// cnt==5 return
if (cnt == 5) {
int mymax = -987654321;
// System.out.println();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (mymap[i][j] > mymax) {
mymax = mymap[i][j];
}
// System.out.print(mymap[i][j] +" ");
}
// System.out.println();
}
MaxValue = Math.max(MaxValue, mymax);
return;
}
// 방향으로 굴려서 보내기
for (int dd = 0; dd < 4; dd++) {
DFS(cnt + 1, dd, mymap);
}
}
}
반응형
'ProgramSoliving' 카테고리의 다른 글
| 백준 : 13548 (0) | 2020.01.30 |
|---|---|
| 백준 : 15686 (0) | 2020.01.29 |
| 백준 : 16235 (0) | 2020.01.28 |
| 백준 : 17140 (0) | 2020.01.28 |
| 백준 : 15683* (0) | 2020.01.21 |