#P8422. [THUPC2022 决赛] 德州消消乐

[THUPC2022 决赛] 德州消消乐

题目背景

众所周知小 c 是开心消消乐的高手,而小 z 玩这种稍微需要动一点脑子的游戏都很不在行。正值五一假期,小 c 闲得无聊就打算来教小 z。

经过五天五夜不间断教学,小 z 终于领悟了一点门道(小 z 内心 os:但凡能拿出一点热情来学概率论……),然而他俩都忽略了这玩意是会玩上瘾的,更关键的是小 z 来自山东,于是他打算融入一点家乡特色……

小 z:”……众所周知德州在山东,那我们就叫它‘德州消消乐’吧!“

小 c 连忙制止道你快算了吧,上次的大杂糅棋局你忘了?再说此德州非彼德州啊喂,这次你要搞就自己搞吧别拉我下水了。

话还没说完,小 z 转手把规则甩给了小 c。

小 c:“真香”。

题目描述

给定大小为 n×mn \times m 的棋盘,记左上角坐标为 (1,1)(1,1) ,右下角坐标为 (n,m)(n,m) 。有不同颜色的棋子共 kk 种,颜色编号为 1k1\sim k 。最初每个格子都有一个棋子。

共有 qq 次操作,每次操作形如交换相邻(在上、下、左、右方向)的两个棋子。在此之后,在同一行或同一列的连续至少 33 个相同颜色的棋子会被消除。

消除后,所有棋子会遵循重力下落,这一列的最上方变成空位。所有棋子下落完成后,如果又产生了能消除的情况,则会触发连锁反应继续消除,直到无法消除为止。称一次消除+一次下落为“一轮消除”,由此可以定义一次操作触发的消除“轮数”。

其中,有些棋子具有特殊属性,被消除时会触发特殊效果,一共有以下 66 类:

  • 1、消除时将同一行的全部棋子消除;
  • 2、消除时将同一列的全部棋子消除;
  • 3、消除时将同一行和同一列的全部棋子消除;
  • 4、消除时将以之为中心 3×33 \times 3 的正方形范围内的棋子全部消除;
  • 5、消除时将以之为中心 5×55 \times 5 的正方形范围内的棋子全部消除;
  • 6、消除时将与之颜色相同的棋子全部消除;

触发一个棋子的特殊效果时可能连锁触发其他棋子的特殊效果,但是这些都是在同一轮消除内触发的(即连锁反应触发的过程中不会引起下落)。

游戏中,每次操作都要求必须有效,即操作的两个位置相邻且均不为空位,且在操作之后能进行棋子的消除。若某此操作并非有效,则直接跳过这一次操作。所有 qq 次操作结束后游戏结束。

定义一次有效操作的“主颜色”为通过交换而直接被消除的颜色(即不包括特殊效果触发和下落引起的消除),容易发现一次有效操作的主颜色至少有 11 种,最多有 22 种。

游戏中,玩家要通过操作来获取尽可能多的得分。得分的规则有如下 55 种:消除奖分+连锁奖分+组合奖分+牌型奖分+终局奖分。

  • 消除奖分:每次有效操作中,第 ii 轮消除的消除奖分为这一轮中所有被消除的棋子的颜色编号之和的 ii 倍。

  • 连锁奖分:设某次有效操作的总消除轮数为 xx ,则有连锁奖分 80(x1)280(x-1)^2

  • 组合奖分:某一轮消除中,在仅考虑由“同一行或同一列至少连续 33 个相同颜色”引发的消除的情况下(即不考虑所有特殊效果引起的消除),设某个被消除的同色四连通块大小为 xx ,则有组合奖分 50(x3)250(x-3)^2 。如: 44 个同色棋子组成四连的组合奖分为 505055 个同色棋子组成五连、十字或T字等形状的组合奖分为 2002002×32\times3 的方形同色棋子的组合奖分为 450450

  • 牌型奖分:每 55 次有效操作计算一次牌型奖分,取之前 55 次有效操作的主颜色(若某次操作有多个主颜色,取能按照以下规则计算出的最大奖分的主颜色),按照如下牌型规则计算奖分:

    • 高牌: 55 种颜色全部不同,奖 5050 分 + 所有牌中最大的颜色编号;

    • 一对: 22 个相同颜色 + 33 个不同颜色,奖 100100 分 + 一对的颜色编号 ×2\times 2

    • 两对: 22 对相同颜色 + 11 个其他颜色,奖 200200 分 + 两对中较大的颜色编号 ×2\times 2 + 两对中较小的颜色编号;

    • 三条: 33 个相同颜色 + 22 个不同颜色,奖 300300 分 + 三条的颜色编号 ×3\times 3

    • 葫芦: 33 个相同颜色 + 另外 22 个相同颜色,奖 500500 分 + 三个相同的颜色编号 ×3\times 3 + 两个相同的颜色编号;

    • 四条: 44 个相同颜色 + 11 个其他颜色,奖 750750 分 + 四条的颜色编号 ×5\times 5

    • 五条: 55 个颜色全部相同,奖 10001000 分 + 五条的颜色编号 ×10\times 10

  • 终局奖分:若所有 qq 次操作均有效,在终局时额外获得 10001000 分终局奖分;若游戏结束时棋盘被全部清空,额外获得 1000010000 分的终局奖分。

给定一局游戏的初始局面和玩家的每一次操作,你需要计算玩家的总得分。

输入格式

11 行: 44 个正整数 n,m,k,qn,m,k,q

接下来 nn 行,每行 mm 个正整数 ai,ja_{i,j} ,表示初始状态下,从上往下第 ii 行、从左往右第 jj 列的棋子的颜色。

接下来 nn 行,每行 mm 个非负整数 bi,jb_{i,j} ,表示初始状态下,从上往下第 ii 行、从左往右第 jj 列的棋子的特殊效果,含义如题面所述。特别地, bi,j=0b_{i,j}=0 表示没有特殊效果。

接下来 qq 行,每行 44 个正整数 xi,1,yi,1,xi,2,yi,2x_{i,1},y_{i,1},x_{i,2},y_{i,2} ,表示交换坐标 (xi,1,yi,1)(x_{i,1},y_{i,1})(xi,2,yi,2)(x_{i,2},y_{i,2}) 位置的棋子。

输出格式

输出一行,一个非负整数表示终局时的总得分。

8 8 5 5
1 1 5 1 5 4 5 3
2 1 2 2 5 4 3 2
1 4 1 4 2 1 5 4
2 1 5 5 2 1 4 4
2 3 5 2 3 4 2 2
4 2 4 3 3 2 4 5
1 3 4 3 5 2 4 3
3 4 2 5 2 1 1 2
0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 6 0 0 3 1
0 0 0 0 3 0 0 0
0 0 0 0 0 0 1 4
3 2 4 2
5 4 5 5
7 2 7 3
8 5 8 6
6 7 6 8

11692

8 8 5 8
1 1 5 1 5 4 5 3
2 1 2 2 5 4 3 2
1 4 1 4 2 1 5 4
2 1 5 5 2 1 4 4
2 3 5 2 3 4 2 2
4 2 4 3 3 2 4 5
1 3 4 3 5 2 4 3
3 4 2 5 2 1 1 2
0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 6 0 0 3 1
0 0 0 0 3 0 0 0
0 0 0 0 0 0 0 0
1 1 2 2
3 2 4 2
3 2 3 3
4 2 4 3
5 4 5 5
7 2 7 3
8 5 8 6
6 7 6 8

684

5 5 2 1
1 1 2 1 1
1 1 2 1 1
2 2 1 2 2
1 1 2 1 1
1 1 2 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
3 3 4 3

3023

提示

【样例 1 解释】

每次操作后,前 33 类奖分的和分别为:315, 417, 429, 435, 482315,\ 417,\ 429,\ 435,\ 482 。第 55 次操作后计算牌型奖分,最优牌型为 (1 2 4 2 4)(1\ 2\ 4\ 2\ 4) ,奖分为 200+4×2+2×1=210200 + 4\times 2 + 2 \times 1 = 210 。终局时两种终局奖分均可获得,故总分为 1169211692

【样例 2 解释】

与上一组样例相比,增加了 33 次无效操作,且最后不能实现全消,因此得不到终局奖分。

【数据范围与约定】

$n,m\leq 50,\ k \leq 100,\ q \leq 1000,\ a_{i,j} \leq k,\ b_{i,j} \leq 6,\ x_{i,1},x_{i,2} \leq n,\ y_{i,1},y_{i,2} \leq m$ 。

保证初始局面没有可以直接消除的情况。