[THUPC2022 决赛] 德州消消乐

题目背景

众所周知小 c 是开心消消乐的高手,而小 z 玩这种稍微需要动一点脑子的游戏都很不在行。正值五一假期,小 c 闲得无聊就打算来教小 z。 经过五天五夜不间断教学,小 z 终于领悟了一点门道(小 z 内心 os:但凡能拿出一点热情来学概率论……),然而他俩都忽略了这玩意是会玩上瘾的,更关键的是小 z 来自山东,于是他打算融入一点家乡特色…… 小 z:”……众所周知德州在山东,那我们就叫它‘德州消消乐’吧!“ 小 c 连忙制止道你快算了吧,上次的大杂糅棋局你忘了?再说此德州非彼德州啊喂,这次你要搞就自己搞吧别拉我下水了。 话还没说完,小 z 转手把规则甩给了小 c。 小 c:“真香”。

题目描述

给定大小为 $n \times m$ 的棋盘,记左上角坐标为 $(1,1)$ ,右下角坐标为 $(n,m)$ 。有不同颜色的棋子共 $k$ 种,颜色编号为 $1\sim k$ 。最初每个格子都有一个棋子。 共有 $q$ 次操作,每次操作形如交换相邻(在上、下、左、右方向)的两个棋子。在此之后,在同一行或同一列的连续至少 $3$ 个相同颜色的棋子会被消除。 消除后,所有棋子会遵循重力下落,这一列的最上方变成空位。所有棋子下落完成后,如果又产生了能消除的情况,则会触发连锁反应继续消除,直到无法消除为止。称一次消除+一次下落为“一轮消除”,由此可以定义一次操作触发的消除“轮数”。 其中,有些棋子具有特殊属性,被消除时会触发特殊效果,一共有以下 $6$ 类: - 1、消除时将同一行的全部棋子消除; - 2、消除时将同一列的全部棋子消除; - 3、消除时将同一行和同一列的全部棋子消除; - 4、消除时将以之为中心 $3 \times 3$ 的正方形范围内的棋子全部消除; - 5、消除时将以之为中心 $5 \times 5$ 的正方形范围内的棋子全部消除; - 6、消除时将与之颜色相同的棋子全部消除; 触发一个棋子的特殊效果时可能连锁触发其他棋子的特殊效果,但是这些都是在同一轮消除内触发的(即连锁反应触发的过程中不会引起下落)。 游戏中,每次操作都要求必须有效,即操作的两个位置相邻且均不为空位,且在操作之后能进行棋子的消除。若某此操作并非有效,则直接跳过这一次操作。所有 $q$ 次操作结束后游戏结束。 定义一次有效操作的“主颜色”为通过交换而直接被消除的颜色(即不包括特殊效果触发和下落引起的消除),容易发现一次有效操作的主颜色至少有 $1$ 种,最多有 $2$ 种。 游戏中,玩家要通过操作来获取尽可能多的得分。得分的规则有如下 $5$ 种:消除奖分+连锁奖分+组合奖分+牌型奖分+终局奖分。 - 消除奖分:每次有效操作中,第 $i$ 轮消除的消除奖分为这一轮中所有被消除的棋子的颜色编号之和的 $i$ 倍。 - 连锁奖分:设某次有效操作的总消除轮数为 $x$ ,则有连锁奖分 $80(x-1)^2$ 。 - 组合奖分:某一轮消除中,在仅考虑由“同一行或同一列至少连续 $3$ 个相同颜色”引发的消除的情况下(即不考虑所有特殊效果引起的消除),设某个被消除的同色四连通块大小为 $x$ ,则有组合奖分 $50(x-3)^2$ 。如: $4$ 个同色棋子组成四连的组合奖分为 $50$ ,$5$ 个同色棋子组成五连、十字或T字等形状的组合奖分为 $200$ ,$2\times3$ 的方形同色棋子的组合奖分为 $450$ 。 - 牌型奖分:每 $5$ 次有效操作计算一次牌型奖分,取之前 $5$ 次有效操作的主颜色(若某次操作有多个主颜色,取能按照以下规则计算出的最大奖分的主颜色),按照如下牌型规则计算奖分: - 高牌: $5$ 种颜色全部不同,奖 $50$ 分 + 所有牌中最大的颜色编号; - 一对: $2$ 个相同颜色 + $3$ 个不同颜色,奖 $100$ 分 + 一对的颜色编号 $\times 2$ ; - 两对: $2$ 对相同颜色 + $1$ 个其他颜色,奖 $200$ 分 + 两对中较大的颜色编号 $\times 2$ + 两对中较小的颜色编号; - 三条: $3$ 个相同颜色 + $2$ 个不同颜色,奖 $300$ 分 + 三条的颜色编号 $\times 3$ ; - 葫芦: $3$ 个相同颜色 + 另外 $2$ 个相同颜色,奖 $500$ 分 + 三个相同的颜色编号 $\times 3$ + 两个相同的颜色编号; - 四条: $4$ 个相同颜色 + $1$ 个其他颜色,奖 $750$ 分 + 四条的颜色编号 $\times 5$ ; - 五条: $5$ 个颜色全部相同,奖 $1000$ 分 + 五条的颜色编号 $\times 10$ 。 - 终局奖分:若所有 $q$ 次操作均有效,在终局时额外获得 $1000$ 分终局奖分;若游戏结束时棋盘被全部清空,额外获得 $10000$ 分的终局奖分。 给定一局游戏的初始局面和玩家的每一次操作,你需要计算玩家的总得分。

输入输出格式

输入格式


第 $1$ 行: $4$ 个正整数 $n,m,k,q$ 。 接下来 $n$ 行,每行 $m$ 个正整数 $a_{i,j}$ ,表示初始状态下,从上往下第 $i$ 行、从左往右第 $j$ 列的棋子的颜色。 接下来 $n$ 行,每行 $m$ 个非负整数 $b_{i,j}$ ,表示初始状态下,从上往下第 $i$ 行、从左往右第 $j$ 列的棋子的特殊效果,含义如题面所述。特别地, $b_{i,j}=0$ 表示没有特殊效果。 接下来 $q$ 行,每行 $4$ 个正整数 $x_{i,1},y_{i,1},x_{i,2},y_{i,2}$ ,表示交换坐标 $(x_{i,1},y_{i,1})$ 和 $(x_{i,2},y_{i,2})$ 位置的棋子。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

11692

输入样例 #2

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

输出样例 #2

684

输入样例 #3

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

输出样例 #3

3023

说明

【样例 1 解释】 每次操作后,前 $3$ 类奖分的和分别为:$315,\ 417,\ 429,\ 435,\ 482$ 。第 $5$ 次操作后计算牌型奖分,最优牌型为 $(1\ 2\ 4\ 2\ 4)$ ,奖分为 $200 + 4\times 2 + 2 \times 1 = 210$ 。终局时两种终局奖分均可获得,故总分为 $11692$ 。 【样例 2 解释】 与上一组样例相比,增加了 $3$ 次无效操作,且最后不能实现全消,因此得不到终局奖分。 【数据范围与约定】 $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$ 。 保证初始局面没有可以直接消除的情况。