{"problem":{"name":"[THUPC 2022 决赛] 德州消消乐","description":{"content":"给定大小为 $n \\times m$ 的棋盘，记左上角坐标为 $(1,1)$ ，右下角坐标为 $(n,m)$ 。有不同颜色的棋子共 $k$ 种，颜色编号为 $1\\sim k$ 。最初每个格子都有一个棋子。 共有 $q$ 次操作，每次操作形如交换相邻（在上、下、左、右方向）的两个棋子。在此之后，在同一行或同一列的连续至少 $3$ 个相同颜色的棋子会被消除。 消除后，所有棋子会遵循重力下落，这一列","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8422"},"statements":[{"statement_type":"Markdown","content":"给定大小为 $n \\times m$ 的棋盘，记左上角坐标为 $(1,1)$ ，右下角坐标为 $(n,m)$ 。有不同颜色的棋子共 $k$ 种，颜色编号为 $1\\sim k$ 。最初每个格子都有一个棋子。\n\n共有 $q$ 次操作，每次操作形如交换相邻（在上、下、左、右方向）的两个棋子。在此之后，在同一行或同一列的连续至少 $3$ 个相同颜色的棋子会被消除。\n\n消除后，所有棋子会遵循重力下落，这一列的最上方变成空位。所有棋子下落完成后，如果又产生了能消除的情况，则会触发连锁反应继续消除，直到无法消除为止。称一次消除+一次下落为“一轮消除”，由此可以定义一次操作触发的消除“轮数”。\n\n其中，有些棋子具有特殊属性，被消除时会触发特殊效果，一共有以下 $6$ 类：\n\n- 1、消除时将同一行的全部棋子消除；\n- 2、消除时将同一列的全部棋子消除；\n- 3、消除时将同一行和同一列的全部棋子消除；\n- 4、消除时将以之为中心 $3 \\times 3$ 的正方形范围内的棋子全部消除；\n- 5、消除时将以之为中心 $5 \\times 5$ 的正方形范围内的棋子全部消除；\n- 6、消除时将与之颜色相同的棋子全部消除； \n\n触发一个棋子的特殊效果时可能连锁触发其他棋子的特殊效果，但是这些都是在同一轮消除内触发的（即连锁反应触发的过程中不会引起下落）。\n\n游戏中，每次操作都要求必须有效，即操作的两个位置相邻且均不为空位，且在操作之后能进行棋子的消除。若某次操作并非有效，则直接跳过这一次操作。所有 $q$ 次操作结束后游戏结束。\n\n定义一次有效操作的“主颜色”为通过交换而直接被消除的颜色（即不包括特殊效果触发和下落引起的消除），容易发现一次有效操作的主颜色至少有 $1$ 种，最多有 $2$ 种。\n\n游戏中，玩家要通过操作来获取尽可能多的得分。得分的规则有如下 $5$ 种：消除奖分+连锁奖分+组合奖分+牌型奖分+终局奖分。\n\n- 消除奖分：每次有效操作中，第 $i$ 轮消除的消除奖分为这一轮中所有被消除的棋子的颜色编号之和的 $i$ 倍。\n- 连锁奖分：设某次有效操作的总消除轮数为 $x$ ，则有连锁奖分 $80(x-1)^2$ 。\n- 组合奖分：某一轮消除中，在仅考虑由“同一行或同一列至少连续 $3$ 个相同颜色”引发的消除的情况下（即不考虑所有特殊效果引起的消除），设某个被消除的同色四连通块大小为 $x$ ，则有组合奖分 $50(x-3)^2$ 。如： $4$ 个同色棋子组成四连的组合奖分为 $50$ ，$5$ 个同色棋子组成五连、十字或T字等形状的组合奖分为 $200$ ，$2\\times3$ 的方形同色棋子的组合奖分为 $450$ 。\n - 牌型奖分：每 $5$ 次有效操作计算一次牌型奖分，取之前 $5$ 次有效操作的主颜色（若某次操作有多个主颜色，取能按照以下规则计算出的最大奖分的主颜色），按照如下牌型规则计算奖分：\n   \n   - 高牌： $5$ 种颜色全部不同，奖 $50$ 分 + 所有牌中最大的颜色编号；\n   - 一对： $2$ 个相同颜色 + $3$ 个不同颜色，奖 $100$ 分 + 一对的颜色编号 $\\times 2$ ；\n   \n   - 两对： $2$ 对相同颜色 + $1$ 个其他颜色，奖 $200$ 分 + 两对中较大的颜色编号 $\\times 2$ + 两对中较小的颜色编号；\n   - 三条： $3$ 个相同颜色 + $2$ 个不同颜色，奖 $300$ 分 + 三条的颜色编号 $\\times 3$ ；\n   - 葫芦： $3$ 个相同颜色 + 另外 $2$ 个相同颜色，奖 $500$ 分 + 三个相同的颜色编号 $\\times 3$ + 两个相同的颜色编号；\n   - 四条： $4$ 个相同颜色 + $1$ 个其他颜色，奖 $750$ 分 + 四条的颜色编号 $\\times 5$ ；\n   - 五条： $5$ 个颜色全部相同，奖 $1000$ 分 + 五条的颜色编号 $\\times 10$ 。\n - 终局奖分：若所有 $q$ 次操作均有效，在终局时额外获得 $1000$ 分终局奖分；若游戏结束时棋盘被全部清空，额外获得 $10000$ 分的终局奖分。\n\n给定一局游戏的初始局面和玩家的每一次操作，你需要计算玩家的总得分。\n\n## Input\n\n第 $1$ 行： $4$ 个正整数 $n,m,k,q$ 。\n\n接下来 $n$ 行，每行 $m$ 个正整数 $a_{i,j}$ ，表示初始状态下，从上往下第 $i$ 行、从左往右第 $j$ 列的棋子的颜色。\n\n接下来 $n$ 行，每行 $m$ 个非负整数 $b_{i,j}$ ，表示初始状态下，从上往下第 $i$ 行、从左往右第 $j$ 列的棋子的特殊效果，含义如题面所述。特别地， $b_{i,j}=0$ 表示没有特殊效果。\n\n接下来 $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\n## Output\n\n输出一行，一个非负整数表示终局时的总得分。\n\n[samples]\n\n## Background\n\n众所周知小 c 是开心消消乐的高手，而小 z 玩这种稍微需要动一点脑子的游戏都很不在行。正值五一假期，小 c 闲得无聊就打算来教小 z。\n\n经过五天五夜不间断教学，小 z 终于领悟了一点门道（小 z 内心 os：但凡能拿出一点热情来学概率论……），然而他俩都忽略了这玩意是会玩上瘾的，更关键的是小 z 来自山东，于是他打算融入一点家乡特色……\n\n小 z：”……众所周知德州在山东，那我们就叫它‘德州消消乐’吧！“\n\n小 c 连忙制止道你快算了吧，上次的大杂糅棋局你忘了？再说此德州非彼德州啊喂，这次你要搞就自己搞吧别拉我下水了。\n\n话还没说完，小 z 转手把规则甩给了小 c。\n\n小 c：“真香”。\n\n## Note\n\n【样例 1 解释】\n\n每次操作后，前 $3$ 类奖分的和分别为：$315,\\ 417,\\ 429,\\ 435,\\ 482$ 。第 $5$ 次操作后计算牌型奖分，最优牌型为 $(1\\ 2\\ 4\\ 2\\ 4)$ ，奖分为 $200 + 4\\times 2 + 2 \\times 1 = 210$ 。终局时两种终局奖分均可获得，故总分为 $11692$ 。\n\n【样例 2 解释】\n\n与上一组样例相比，增加了 $3$ 次无效操作，且最后不能实现全消，因此得不到终局奖分。\n\n【数据范围与约定】\n\n$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$ 。\n\n保证初始局面没有可以直接消除的情况。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8422","tags":["模拟","2022","O2优化","THUPC"],"sample_group":[["8 8 5 5\n1 1 5 1 5 4 5 3\n2 1 2 2 5 4 3 2\n1 4 1 4 2 1 5 4\n2 1 5 5 2 1 4 4\n2 3 5 2 3 4 2 2\n4 2 4 3 3 2 4 5\n1 3 4 3 5 2 4 3\n3 4 2 5 2 1 1 2\n0 0 0 0 0 0 0 0\n2 0 0 0 0 0 0 0\n0 0 0 0 5 0 0 0\n0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0\n0 0 0 6 0 0 3 1\n0 0 0 0 3 0 0 0\n0 0 0 0 0 0 1 4\n3 2 4 2\n5 4 5 5\n7 2 7 3\n8 5 8 6\n6 7 6 8\n","11692\n"],["8 8 5 8\n1 1 5 1 5 4 5 3\n2 1 2 2 5 4 3 2\n1 4 1 4 2 1 5 4\n2 1 5 5 2 1 4 4\n2 3 5 2 3 4 2 2\n4 2 4 3 3 2 4 5\n1 3 4 3 5 2 4 3\n3 4 2 5 2 1 1 2\n0 0 0 0 0 0 0 0\n2 0 0 0 0 0 0 0\n0 0 0 0 5 0 0 0\n0 0 0 0 0 0 0 0\n0 0 0 0 0 0 0 0\n0 0 0 6 0 0 3 1\n0 0 0 0 3 0 0 0\n0 0 0 0 0 0 0 0\n1 1 2 2\n3 2 4 2\n3 2 3 3\n4 2 4 3\n5 4 5 5\n7 2 7 3\n8 5 8 6\n6 7 6 8\n","684\n"],["5 5 2 1\n1 1 2 1 1\n1 1 2 1 1\n2 2 1 2 2\n1 1 2 1 1\n1 1 2 1 1\n0 0 0 0 0\n0 0 0 0 0\n0 0 0 0 0\n0 0 0 0 0\n0 0 0 0 0\n3 3 4 3\n","3023\n"]],"created_at":"2026-03-03 11:09:25"}}