#P18941. [Mladen Manev 2020 A2] puzzle / 拼图计数
[Mladen Manev 2020 A2] puzzle / 拼图计数
拼图计数(Puzzle)
题目描述
给定一个 行 列的网格,它已经被 个有编号的拼图块填好。每块拼图占据若干个通过公共边连通的格子,编号为 。某些格子禁止覆盖。
你可以移动每个拼图块,并将它旋转任意多个90度,也可以翻面。因此每块允许其形状的所有旋转与镜像变换。
要求每个拼图块恰好使用一次,恰好覆盖所有允许格子,既不能重叠,也不能覆盖禁止格子。求不同摆法的数量。拼图块带有编号;交换两个形状相同但编号不同的拼图块,视为不同摆法。同一块由于自身对称性产生相同的占据位置时,只计算一次。
保证所有拼图块在网格中合法放置方式的数量之和不超过1000,最终答案也不超过1000。
输入格式
第一行三个整数 。
接下来 行,每行 个整数,给出最初的一个合法摆法。正整数表示该格子所属的拼图块编号,0表示禁止覆盖。
输出格式
输出不同合法摆法的数量。
数据范围
,,。
样例
3 3 3
1 1 1
2 0 3
2 2 3
8
整理说明
原文输入段落误写为“四个自然数”,但只列出 ;这里按官方程序和测试数据使用三个整数。
来源与数据说明
2020 年 Dr. Mladen Manev,A2,原题名 puzzle。赛事资料,原文题面见附件 statement.pdf。
本题使用官方原始测试数据;评测接口按本站环境适配。总分为 100 分。