19961: 最大点数(外太空2048)
http://cs101.openjudge.cn/practice/19961/
2048是一款不用念诗能够实现时间跳跃的小游戏（参考https://2048game.com），只需玩5分钟，就可以跳到两小时后的世界。J同学在进行了上百次时间穿越后，得到灵感设计了一款新游戏，规则如下。 接近原2048规则（重力作用）中移动方块和增加点数的方法不变，棋盘从44变成mn型，开始时棋盘上即摆放了一些不同点数的方块，但每次移动后不会生成新的方块。在有限的操作次数（往上/下/左/右方向上移动一次记为一次操作）内，得到更高点数（即所有方块中点数最高者）。
Note: 我们的2048，是在外太空玩的，不符合重力作用，规则如下图。 
输入
第一行：整数m与n（2 <= m, n <= 10）,最大操作次数p（1 <= p <= 6）。空格分隔。 之后m行：空格分隔的n个整数，代表每一格上方块的点数（2, 4, 8, 16, ..., 1024）。若为0，则表示此格没有方块。这m行输入保证不全为0（即不会输入空棋盘）。
输出
一个整数，代表p次操作内能得到的最高点数。
样例输入
Sample1 Input:
4 4 2
2 4 512 16
2 128 16 16
2 8 256 0
2 512 256 2
Sample1 Output:
1024
解释：第一步，向下移动，变成
0 4 0 0
0 128 512 0
4 8 16 32
4 512 512 2
第二步，向左移动，将第4行两个512拼合得到1024。
Sample2 Input:
2 4 2
2 2 4 4
0 0 8 2
Sample2 Output:
16
# 一步2 2 4 4 -> 4 4 4 -> 8 4，得0 0 8 4，第二步向下就有16。样例输出
Sample3 Input:
2 3 6
2 4 4
32 16 8
Sample3 Output:
64
# 第一步，向右移动，第二步，向下移动，第三步，向左移动，第四步，向左移动。
后两步无论怎样移动最大值都是64。
Sample4 Input:
4 3 5
32 256 128
256 128 64
32 64 128
256 128 256
Sample4 Output:
256
# 此局面如何移动都不会变，故最大值为256。提示
在太空，没有阻力，所以都是完全非弹性碰撞。 碰撞后，尾部算起的相同的两个数字先黏结。因为在外太空没有能量损失， 黏结后，如果尾部算起还有两个数字相同，可以继续黏结。如样例2所示。
来源: cs101-2019 胡康德龙
辛苦了一下午加一晚上。
python
# 23工学院 谢宇翔
import copy
import sys
sys.setrecursionlimit(1<<30)
m,n,p=map(int,input().split())
matrix=[]
for _ in range(m):
matrix.append(list(map(int,input().split())))
def add(lst):
for i in range(len(lst)-1):
if lst[i]!=0:
for j in range(i+1,len(lst)):
if lst[i]==lst[j]:
lst[i],lst[j]=0,2*lst[i]
break
elif lst[j]==0:
pass
else:
break
ans=[]
count=0
for i in lst:
if i!=0:
ans.append(i)
count+=1
return [0]*(len(lst)-count)+ans
def move(matrix,dirc):
new=copy.deepcopy(matrix)
if dirc=="right":
for i in range(m):
newrow=add(new[i])
new[i]=newrow
elif dirc=="down":
for j in range(n):
temp=[new[i][j] for i in range(m)]
newline=add(temp)
for k in range(m):
new[k][j]=newline[k]
elif dirc=="left":
for i in range(m):
temp=[new[i][j] for j in range(n-1,-1,-1)]
newrow=add(temp)
for k in range(n):
new[i][n-1-k]=newrow[k]
else:
for j in range(n):
temp=[new[i][j] for i in range(m-1,-1,-1)]
newline=add(temp)
for k in range(m):
new[m-1-k][j]=newline[k]
return new
result=0
def calculate(matrix,num):
global result
if num==p:
result=max(result,max(max(matrix[i]) for i in range(m)))
return
calculate(move(matrix,"up"),num+1)
calculate(move(matrix,"down"),num+1)
calculate(move(matrix,"left"),num+1)
calculate(move(matrix,"right"),num+1)
calculate(matrix,0)
print(result)python
# 2023，蒋子轩
def slide_and_combine(board, reverse=False, vertical=False):
result = []
for line in zip(*board) if vertical else board:
if reverse:
line = line[::-1]
new_line = [i for i in line if i != 0]
i = len(new_line) - 1
while i>0:
if new_line[i] == new_line[i - 1]:
new_line[i - 1] *= 2
del new_line[i]
i -= 1
new_line += [0] * (len(line) - len(new_line))
result.append(new_line[::-1] if reverse else new_line)
return list(zip(*result)) if vertical else result
def max_score(board, moves):
if moves == 0:
return max(max(row) for row in board)
best_score = max(max(row) for row in board)
for vertical, reverse in [(False, False), (False, True), (True, False), (True, True)]:
new_board = slide_and_combine(board, reverse, vertical)
best_score = max(best_score, max_score(new_board, moves - 1))
return best_score
m, n, moves = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(m)]
print(max_score(board, moves))python
# 23 黄原明 化院
# 测试数据小，可以任人摆布？直接枚举？
from itertools import product
from copy import deepcopy
m,n,p=map(int,input().split())
board=[list(map(int,input().split())) for i in range(m)]
def turn(board,dirt):
if dirt==2:
changed = 0
while True:
c = 0
for i in range(m):
for j in range(n - 1, 0, -1):
if board[i][j] > 0 and board[i][j - 1] == 0:
board[i][j], board[i][j - 1] = 0, board[i][j]
c = 1
changed = c
if not c:
break
for i in range(m):
for j in range(n - 1, 0, -1):
if board[i][j] == board[i][j - 1]:
board[i][j - 1] *= 2
board[i][j] = 0
changed = 1
while True:
c = 0
for i in range(m):
for j in range(n - 1, 0, -1):
if board[i][j] > 0 and board[i][j - 1] == 0:
board[i][j], board[i][j - 1] = 0, board[i][j]
c = 1
if not c:
break
return changed
elif dirt==3:
changed = 0
while True:
c = 0
for i in range(m):
for j in range(0,n-1):
if board[i][j] > 0 and board[i][j+1] == 0:
board[i][j], board[i][j+1] = 0, board[i][j]
c = 1
changed = c
if not c:
break
for i in range(m):
for j in range(0,n-1):
if board[i][j] == board[i][j+1]:
board[i][j+1] *= 2
board[i][j] = 0
changed = 1
while True:
c = 0
for i in range(m):
for j in range(0,n-1):
if board[i][j] > 0 and board[i][j+1] == 0:
board[i][j], board[i][j+1] = 0, board[i][j]
c = 1
if not c:
break
return changed
elif dirt==0:
changed = 0
while True:
c = 0
for i in range(m-1,0,-1):
for j in range(n):
if board[i][j] > 0 and board[i-1][j] == 0:
board[i][j], board[i-1][j] = 0, board[i][j]
c = 1
changed = c
if not c:
break
for i in range(m-1,0,-1):
for j in range(n):
if board[i][j] == board[i-1][j]:
board[i-1][j] *= 2
board[i][j] = 0
changed = 1
while True:
c = 0
for i in range(m-1,0,-1):
for j in range(n):
if board[i][j] > 0 and board[i-1][j] == 0:
board[i][j], board[i-1][j] = 0, board[i][j]
c = 1
if not c:
break
return changed
elif dirt == 1:
changed = 0
while True:
c = 0
for i in range(0,m-1):
for j in range(n):
if board[i][j] > 0 and board[i+1][j] == 0:
board[i][j], board[i+1][j] = 0, board[i][j]
c = 1
changed = c
if not c:
break
for i in range(0,m-1):
for j in range(n):
if board[i][j] == board[i+1][j]:
board[i+1][j] *= 2
board[i][j] = 0
changed = 1
while True:
c = 0
for i in range(0,m-1):
for j in range(n):
if board[i][j] > 0 and board[i+1][j] == 0:
board[i][j], board[i+1][j] = 0, board[i][j]
c = 1
if not c:
break
return changed
#用枚举法解，这样最多4096种情况
max_=0
for i in product(range(4),repeat=p):
mx=deepcopy(board)
i=list(i)
for dirt in i:
turn(mx,dirt)
max__=0
for a in range(m):
for b in range(n):
if mx[a][b]>max__:
max__=mx[a][b]
if max__>max_:
max_=max__
print(max_)