德州消消乐 - 题目

题目背景

众所周知小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})$ 位置的棋子。

数据范围：$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$ 。保证初始局面没有可以直接消除的情况。

输出格式

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

样例数据

样例 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 输出

样例 1 解释

每次操作后，前 $3$ 类奖分的和分别为：$315,\ 417,\ 429,\ 435,\ 482$ 。第 $5$ 次操作后计算牌型奖分，最优牌型为 $(1\ 2\ 4\ 2\ 4)$ ，奖分为 $200 + 4\times 2 + 2 \times 1 = 210$ 。终局时两种终局奖分均可获得，故总分为 $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 输出

样例 2 解释

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

样例 3 输入

QOJ.ac

QOJ

# 4323. 德州消消乐