#P2669. [cqoi2012]局部极小值

    ID: 1726 传统题 1000ms 512MiB 尝试: 1169 已通过: 499 难度: 8 上传者: 标签>CF2400提高+/省选-容斥原理独立集回溯搜索可行性剪枝状压 DP位集求并滚动数组

[cqoi2012]局部极小值

题目描述

有一个 nn 行 mm 列的整数矩阵,其中 11 到 n×mn\times m 之间的每个整数恰好出现一次。

如果一个格子比所有相邻格子(相邻是指有公共边或公共顶点)都小,我们说这个格子是局部极小值。给出所有局部极小值的位置,你的任务是判断有多少个可能的矩阵。

答案对 1234567812345678 取模。

输入格式

输入第一行包含两个整数 nn 和 mm,即行数和列数。

以下 nn 行每行 mm 个字符,第 (i+1)(i + 1) 行的第 jj 个字符代表第 ii 列的第 jj 个格子是否是局部极小值,该字符只可能是 X 或 .,其中 X 表示局部极小值,. 表示非局部极小值。

输出格式

输出仅一行,为可能的矩阵总数除以 1234567812345678 的余数。

样例 #1

样例输入 #1

3 2
X.
..
.X

样例输出 #1

60

数据规模与约定

  • 对于 100%100\% 的数据,保证 1≤n≤41\le n\le4,1≤m≤71\le m\le7。