#P2497. Winmine.exe

    ID: 1552 传统题 1000ms 256MiB 尝试: 6 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-洪水填充半边面遍历全子集枚举断环成链状压 DP计数 DP滚动数组预计算转移分组背包阶乘逆元预处理

Winmine.exe

P2497 Winmine.exe(扫雷方案计数)

题目背景

Windows 扫雷是一款经典游戏。棋盘中的每个格子要么埋有一颗地雷,要么没有地雷。玩家可以揭开安全格子;若一个安全格子周围有地雷,揭开后将显示数字,表示它周围八个方向相邻格子中的地雷数量。数字 0 表示周围没有地雷。

在游戏进行到某个状态时,部分格子已经揭开,剩余格子仍未揭开。仅凭当前揭示的数字,有时无法唯一确定地雷的位置。

你的任务是:已知棋盘当前状态以及整个棋盘中的地雷总数,计算所有与当前已揭示数字一致的地雷分布方案数。

每个未揭示格子最多有一颗地雷;已经揭示数字的格子必然安全。不同的地雷位置集合视为不同方案。

题目描述

给定一个 n×mn\times m 的扫雷棋盘、地雷总数 MM,以及棋盘当前已揭开的数字格子和未揭示的格子。

  • 字符 0 至 8 表示一个已揭示的安全格子,数字等于该格子周围八个方向(包含对角线)相邻格子中的地雷数。
  • 字符 . 表示一个尚未揭示的格子,可能有地雷,也可能没有。

求有多少种放置恰好 MM 颗地雷的方式,能够满足所有已揭示的数字。输出答案对 10000031000003 取模后的结果。

数据具有以下特殊保证

  1. 给定状态可以由初始棋盘只进行一次点击得到。
  2. 未揭示格子之间若能通过共享边(上、下、左、右)的未揭示格子路径连通,则它们构成的连通部分具有双连通性;即删除该部分中任意一个其他未揭示格子后,原本相关格子仍连通(按原题的表述)。
  3. 对于由正数数字格子(1 至 8)通过共享边连成的一个连通块,与该连通块相邻的全部未揭示格子也必须通过共享边的未揭示格子路径彼此连通。

注意: 计算数字时使用八邻域;上述连通性保证中的“连通”仅使用四邻域,不包括对角线。

输入格式

第一行是正整数 TT,表示测试用例数。

接下来有 TT 组测试数据,每组格式为:

  • 第一行三个整数 n,m,Mn,m,M,分别表示行数、列数和地雷总数。
  • 随后 nn 行,每行恰好 mm 个字符,表示棋盘状态;字符仅为 0~8 或 .。

输出格式

对于第 kk 组测试数据,输出一行:

Case #k: answer

其中 answer 为合法地雷分布方案数对 10000031000003 取模的结果,kk 从 11 开始编号。

数据范围

  • 1≤T≤501\le T\le 50。
  • 1≤n,m≤1001\le n,m\le 100。
  • 1≤M≤15001\le M\le 1500。原始文字曾误写成 M≤1000M\le 1000,官方补充说明更正为 15001500。
  • 每个格子至多一颗地雷。
  • 测试数据满足前述三项特殊保证。

样例输入

2
4 5 2
.....
.....
11111
00000
4 5 4
.....
.....
22222
00000

样例输出

Case #1: 2
Case #2: 1

样例解释

样例一中,第一行和第二行的未揭示格子需要在总共放置两颗地雷的情况下满足所有 1,共有 22 种方案。样例二要求放置四颗地雷并满足所有 2,只有 11 种方案。