Description
有一个n行m列的整数矩阵，其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。
Input
输入第一行包含两个整数n和m（1<=n<=4, 1<=m<=7），即行数和列数。
以下n行每行m个字符，其中“X”表示局部极小值，“.”表示非局部极小值。
Output
输出仅一行，为可能的矩阵总数除以12345678的余数。
Sample Input
3 2
X.
..
.X
Sample Output
60
--
我们考虑把(1~n imes m)依次往矩阵里填
因为局部最小值最多就只有8个，所以我们可以把他们压缩起来
设(f[sta][i])表示填到第i个数，局部最小值的填写状态为sta的方案数
那么第i个数有两种填写方法，'X'位置和'.'位置
如果填在'X'位置，我们直接填就好，因为我们是按从小到大来填的，那么有(f[sta|(1<<(k-1))][i+1]+=f[sta|(1<<(k-1))][i])
如果填在'.'位置，那么显然有些位置是不能填的，就是那些'X'周围的位置，那么我们可以预处理出每个状态(sta)中可以随便填的位置个数(p[sta])，转移为(f[sta][i+1]+=f[sta][i] imes max(p[sta]-i+1,0))
然后这样算出来也会有问题，因为我们只保证了'X'为局部最小值，没有保证'.'不为局部最小值，那么我们容斥一下即可
（ps：(p[])可以不用预处理，在代码里有注释）
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
const int N=10,p=12345678;
const int dx[9]={-1,-1,-1,0,0,1,1,1,0};
const int dy[9]={-1,0,1,-1,1,-1,0,1,0};
char map[N][N];
int tx[N],ty[N],f[(1<<N)+10][N*N],A[N][N];
int n,m,Ans;
bool in_map(int x,int y){return x>0&&x<=n&&y>0&&y<=m;}
int get(){
int tot=0;
for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) if (map[x][y]=='X') tx[tot]=x,ty[tot]=y,tot++;
memset(f,0,sizeof(f));
memset(A,255,sizeof(A));
f[0][0]=1;
for (int sta=0;sta<1<<tot;sta++){
for (int i=0;i<tot;i++)
if (!(sta&(1<<i)))
for (int k=0;k<9;k++)
if (in_map(tx[i]+dx[k],ty[i]+dy[k]))
A[tx[i]+dx[k]][ty[i]+dy[k]]=sta;
int cnt=0;//p[]没必要预处理，开个数组在当前状态存下来即可，因为我是用当前状态更新之后的状态
for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) if (A[x][y]!=sta) cnt++;
for (int i=0;i<=n*m;i++){
if (f[sta][i]){
f[sta][i+1]=(f[sta][i+1]+f[sta][i]*max(cnt-i,0))%p;
for (int j=0;j<tot;j++)
if (!(sta&(1<<j)))
f[sta|(1<<j)][i+1]=(f[sta|(1<<j)][i+1]+f[sta][i])%p;
}
}
}
return f[(1<<tot)-1][n*m];
}
void search(int x,int y,int k){//容斥搜索
if (x>n){Ans=(Ans+k*get())%p;return;}
if (y>m){search(x+1,1,k);return;}
search(x,y+1,k);
for (int k=0;k<9;k++) if (in_map(x+dx[k],y+dy[k])&&map[x+dx[k]][y+dy[k]]=='X') return;
map[x][y]='X',search(x,y+1,-k),map[x][y]='.';//容斥
}
int solve(){
//首先判非法状态
for (int x=1;x<=n;x++)
for (int y=1;y<=m;y++)
if (map[x][y]=='X')
for (int k=0;k<8;k++)
if (in_map(x+dx[k],y+dy[k])&&map[x+dx[k]][y+dy[k]]=='X')
return 0;
Ans=0;
search(1,1,1);
Ans=(Ans+p)%p;
return Ans;
}
int main(){
n=read(),m=read();
for (int i=1;i<=n;i++) scanf("%s",map[i]+1);
printf("%d
",solve());
return 0;
}