Problem:


Problem D: Smartphone Game

Problem

人気のスマフォゲームの一機能を実装してみよう。ゲームは以下の仕様に基づく。

5*5のマスに、5種類のブロックが設置されている。

それぞれの種類のブロックには得点が設定されている。

得点には、ブロックの得点の他に、ボーナス得点が設定されている。最初のボーナス得点は1である。

ブロックを任意に1つだけ決めて、最大で n 回まで上下左右に移動できる。移動先のブロックは移動元のブロックのあった場所に移動する。つまり、隣接したブロックを交換する事になる。

移動した後、同じ種類のブロックが縦3個以上又は横3個以上に並んだ場合、並んだブロックは全て消える。

消えるべきブロックが全て消えた後、あるブロックの下に別のブロックが存在しない場合、そのブロックは落下する。落下とは、あるブロックの１つ上に辿り着くまで下に移動する事をいう。ブロックが下に存在しない場合は一番下に移動する。

全てのブロックの落下後にボーナス得点が1だけ加算される。

その後にブロックが並んだ場合、さらに消え、落下する。

ブロックが消える時に、ブロック１つにつき「ブロックの得点*ボーナス得点」が自分の得点に加算される。

１回のプレイで得られる最大の点数を求めよ。

Input

入力は複数のデータセットからなる。

各データセットは以下で表される。

n
a11 .. a15
.
.
a51 .. a55
score1 .. score5

aijは1から5までの数字で、ブロックの種類を表す。

scoreiは i 種類目のブロック１つ分の得点を表す。

n = -1 の時、入力が終了する。

Constraints

入力は以下の条件を満たす。

0 ≤ n ≤ 5

1 ≤ aij ≤ 5

0 ≤ scorei ≤ 100

テストケースの数は 10 を超えない。

入力に含まれる値は全て整数である。

Output

各データセット毎に、答えを一行に出力しなさい。

Sample Input

0
1 1 1 5 5
5 5 5 5 5
5 5 1 5 5
5 1 1 1 5
5 5 5 5 5
0 0 0 0 1
2
1 2 3 4 5
2 3 4 5 5
2 3 4 5 5
3 4 5 5 1
5 4 3 2 1
100 99 98 97 96
5
1 2 3 4 5
2 3 4 5 1
1 2 3 4 5
5 4 3 2 1
1 2 3 4 5
99 79 31 23 56
-1

Sample Output

17
2040
926



Sample input:
0
1 1 1 5 5
5 5 5 5 5
5 5 1 5 5
5 1 1 1 5
5 5 5 5 5
0 0 0 0 1
2
1 2 3 4 5
2 3 4 5 5
2 3 4 5 5
3 4 5 5 1
5 4 3 2 1
100 99 98 97 96
5
1 2 3 4 5
2 3 4 5 1
1 2 3 4 5
5 4 3 2 1
1 2 3 4 5
99 79 31 23 56
-1


Sample output:
17
2040
926

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict, deque
from copy import deepcopy
ml = [[0,1],[0,-1],[-1,0],[1,0]]
def main(n):
    def move(fi,mli,y,x):
        f = deepcopy(fi)
        for mi in mli:
            mx,my = ml[mi]
            mx += x
            my += y
            if 0 <= mx <= 4 and 0 <= my <= 4:
                f[y][x], f[my][mx] = f[my][mx], f[y][x]
                x, y = mx, my
            else:
                return False
        return f

    def d(b):
        a = 0
        de = []
        for y in range(5):
            for x in range(5):
                if c[y][x]:
                    val = c[y][x]
                    if y == 4 or y == 0:
                        if x == 4 or x == 0:
                            continue
                        if c[y][x+1] == c[y][x-1] == c[y][x]:
                            de.append((y,x, 0))
                    else:
                        if x == 4 or x == 0:
                            if c[y+1][x] == c[y-1][x] == c[y][x]:
                                de.append((y,x, 1))
                            continue
                        else:
                            if c[y][x+1] == c[y][x-1] == c[y][x]:
                                de.append((y,x, 0))
                            if c[y+1][x] == c[y-1][x] == c[y][x]:
                                de.append((y,x, 1))
        for y,x,di in de:
            for i in range(3):
                if di:
                    if c[y+i-1][x]:
                        a += score[c[y+i-1][x]-1] * b
                        c[y+i-1][x] = 0
                else:
                    if c[y][x-1+i]:
                        a += score[c[y][x-1+i]-1] * b
                        c[y][x-1+i] = 0
        if fall():
            a += d(b+1)
        return a

    def fall():
        f = False
        for x in range(5):
            for y in range(3,-1,-1):
                if c[y][x] and c[y+1][x] == 0:
                    for yi in range(y+1,5):
                        if c[yi][x] == 0:
                             continue
                        yi -= 1
                        break
                    c[yi][x],c[y][x] = c[y][x],c[yi][x]
                    f = True
        return f

    ans = 0
    field = [list(map(int, input().split())) for i in range(5)]
    score = list(map(int, input().split()))
    for i in range(n+1):
        mlis = list(itertools.product(range(4),repeat = i))
        for mli in mlis:
            for y in range(5):
                for x in range(5):
                    c = move(field, mli, y, x)
                    if c:
                        ans = max(ans,d(1))
    print(ans)

while 1:
    n = int(input())
    if n == -1:
        break
    main(n)

Submission status: Accepted

Solution code:
def main():
    while True:
        n = int(input())
        if n == -1:
            break
        mp = [list(map(int, input().split())) for _ in range(5)]
        scores = list(map(int, input().split()))
    
        vec = ((1, 0), (0, -1), (-1, 0), (0, 1))
    
    
        def simulate():
            use_mp = [[mp[y][x] for x in range(5)] for y in range(5)]
            bonus = 1
            score = 0
            while True:
                delete_set = set()
                for y in range(5):
                    for length in range(5, 2, -1):
                        for left in range(5 - length + 1):
                            if use_mp[y][left] == 0:continue
                            if all([use_mp[y][left] == num for num in use_mp[y][left:left+length]]):
                                for add in range(length):
                                    delete_set.add((left + add, y))
    
                for x in range(5):
                    for length in range(5, 2, -1):
                        for top in range(5 - length + 1):
                            if use_mp[top][x] == 0:continue
                            if all([use_mp[top][x] == num for num in [use_mp[y][x] for y in range(top, top + length)]]):
                                for add in range(length):
                                    delete_set.add((x, top + add))
    
                if not delete_set:
                    break
    
                for x, y in delete_set:
                    score += scores[use_mp[y][x] - 1] * bonus
                    use_mp[y][x] = 0
    
                for x in range(5):
                    line = [use_mp[y][x] for y in range(5) if use_mp[y][x] != 0]
                    line = [0] * (5 - len(line)) + line
                    for y in range(5):
                        use_mp[y][x] = line[y]
    
                bonus += 1
    
            return score
    
        def search(x, y, n):
            ret = simulate()
            if n == 0:return ret
            for dx, dy in vec:
                nx, ny = x + dx, y + dy
                if 0 <= nx < 5 and 0 <= ny < 5:
                    mp[y][x], mp[ny][nx] = mp[ny][nx], mp[y][x]
                    ret = max(ret, search(nx, ny, n - 1))
                    mp[y][x], mp[ny][nx] = mp[ny][nx], mp[y][x]
            return ret
    
    
        ans = 0
        for y in range(5):
            for x in range(5):
                ans = max(ans, search(x, y, n))
    
        print(ans)
    
main()