编程题

1784:山谷


时间限制: 1000 ms         内存限制: 262144 KB
提交数:96    通过数: 23

【题目描述】

在一个$n×m$的矩阵中填上$1\\sim nm$的排列。定义一个格子是山谷当且仅当它所填的数字小于所有与它八连通的格子中填的数字。

给定一个$n×m$的字符矩阵,每个格子是.或$X$。问有多少种不同的填数方式满足一个位置是山谷当且仅当字符矩阵中这个位置是$X$。

输出方案数对$998244353$取模的结果。

【输入】

输入包含多组数据,每组数据第一行两个整数$n,m$,接下来$n$行每行$m$个字符表示字符矩阵。

【输出】

每组数据输出一行一个整数表示答案。

【输入样例】

1 3
X.X
2 2
X.
..

【输出样例】

2
6

【提示】

【数据规模】

对于30%的数据,$nm≤9$。

对于另外30%的数据,字符矩阵中每个格子以及与它八连通的所有格子中至少包含$1$个$X$。

对于100%的数据,$1≤n≤4,1≤m≤7$,数据不超过$5$组。

查看答案
赣ICP备20007335号-2