#P18941. [Mladen Manev 2020 A2] puzzle / 拼图计数

[Mladen Manev 2020 A2] puzzle / 拼图计数

拼图计数(Puzzle)

题目描述

给定一个 MM 行 NN 列的网格,它已经被 KK 个有编号的拼图块填好。每块拼图占据若干个通过公共边连通的格子,编号为 1…K1\ldots K。某些格子禁止覆盖。

你可以移动每个拼图块,并将它旋转任意多个90度,也可以翻面。因此每块允许其形状的所有旋转与镜像变换。

要求每个拼图块恰好使用一次,恰好覆盖所有允许格子,既不能重叠,也不能覆盖禁止格子。求不同摆法的数量。拼图块带有编号;交换两个形状相同但编号不同的拼图块,视为不同摆法。同一块由于自身对称性产生相同的占据位置时,只计算一次。

保证所有拼图块在网格中合法放置方式的数量之和不超过1000,最终答案也不超过1000。

输入格式

第一行三个整数 M,N,KM,N,K。

接下来 MM 行,每行 NN 个整数,给出最初的一个合法摆法。正整数表示该格子所属的拼图块编号,0表示禁止覆盖。

输出格式

输出不同合法摆法的数量。

数据范围

1≤MN≤2561\le MN\le256,1≤M,N≤641\le M,N\le64,1≤K≤161\le K\le16。

样例

3 3 3
1 1 1
2 0 3
2 2 3
8

整理说明

原文输入段落误写为“四个自然数”,但只列出 M,N,KM,N,K;这里按官方程序和测试数据使用三个整数。

来源与数据说明

2020 年 Dr. Mladen Manev,A2,原题名 puzzle。赛事资料,原文题面见附件 statement.pdf。

本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。