Game 2048은 4×4 보드에서 혼자 플레이하는 재미있는 게임입니다.
이 문제에서 논의하는 2048 게임은 보드 크기가 N×N이다. 보드의 크기와 보드에 있는 블록의 상태를 고려하여 최대 2048까지 이동할 수 있는 가장 큰 블록의 값을 계산하는 프로그램을 작성하라. 5회 가능합니다.
기입
첫 번째 줄은 보드 크기 N(1 ≤ N ≤ 20)을 지정합니다. 게임 보드의 초기 상태는 두 번째 행부터 시작하여 N 행으로 제공됩니다. 0은 빈 셀을 나타내고 다른 모든 값은 블록을 나타냅니다. 블록에 적힌 숫자는 2보다 크거나 같고 1024보다 작거나 같은 2의 거듭제곱입니다. 최소 하나의 블록이 지정됩니다.
누르다
최대 5번 이동하여 얻을 수 있는 가장 큰 블록을 반환합니다.
2. 문제 해결
모든 경우를 4방향으로 재귀적으로 시도
세 가지 방식으로 어려움을 식별할 수 있습니다.
- 이동의 구현
- 모든 사례를 재귀적으로 검색
- 탐색하는 동안 새 목록 만들기
이를 신중하게 구현하여 코드를 완성했습니다.
from copy import deepcopy
def move(a, d, board):
if d == 0:
for i in range(a):
cnt = 0
for j in range(a - 1, -1, -1):
if board(i)(j):
for jj in range(j + 1, a - cnt):
if board(i)(j) == board(i)(jj):
board(i)(j) = 0
board(i)(jj) *= 2
cnt += 1
break
elif board(i)(jj) and board(i)(j) != board(i)(jj):
cnt += 1
save = board(i)(j)
board(i)(j) = 0
board(i)(jj - 1) = save
break
elif jj == a - cnt - 1:
save = board(i)(j)
board(i)(j) = 0
board(i)(jj) = save
elif d == 1:
for i in range(a):
cnt = 0
for j in range(a):
if board(i)(j):
for jj in range(j - 1, -1 + cnt, -1):
if board(i)(j) == board(i)(jj):
board(i)(j) = 0
board(i)(jj) *= 2
cnt += 1
break
elif board(i)(jj) and board(i)(j) != board(i)(jj):
cnt += 1
save = board(i)(j)
board(i)(j) = 0
board(i)(jj + 1) = save
break
elif jj == cnt:
save = board(i)(j)
board(i)(j) = 0
board(i)(jj) = save
elif d == 2:
for i in range(a):
cnt = 0
for j in range(a - 1, -1, -1):
if board(j)(i):
for jj in range(j + 1, a - cnt):
if board(j)(i) == board(jj)(i):
board(j)(i) = 0
board(jj)(i) *= 2
cnt += 1
break
elif board(jj)(i) and board(j)(i) != board(jj)(i):
cnt += 1
save = board(j)(i)
board(j)(i) = 0
board(jj-1)(i) = save
break
elif jj == a - cnt - 1:
save = board(j)(i)
board(j)(i) = 0
board(jj)(i) = save
elif d == 3:
for i in range(a):
cnt = 0
for j in range(a):
if board(j)(i):
for jj in range(j - 1, -1 + cnt, -1):
if board(j)(i) == board(jj)(i):
board(j)(i) = 0
board(jj)(i) *= 2
cnt += 1
break
elif board(jj)(i) and board(j)(i) != board(jj)(i):
cnt += 1
save = board(j)(i)
board(j)(i) = 0
board(jj + 1)(i) = save
break
elif jj == cnt:
save = board(j)(i)
board(j)(i) = 0
board(jj)(i) = save
def dfs(a, d, lst):
global v
lst1 = deepcopy(lst)
move(n, d, lst1)
if a == 5:
for k in lst1:
v = max(v, max(k))
return
for k in range(4):
dfs(a+1, k, lst1)
n = int(input())
arr = (list(map(int, input().split())) for _ in range(n))
v = 0
for ii in range(4):
arr1 = deepcopy(arr)
dfs(1, ii, arr1)
print(v)