（题目来自洛谷oj）
一天，maze决定对自己的一块n*m的土地进行修建。他希望这块土地共n*m个格子的高度分别是1,2,3,...,n*m-1,n*m。maze又希望能将这一些格子中的某一些拿来建蓄水池，即这个格子的高度应该比它周围8个格子的高度都小（超出土地范围的格子的高度算作无穷大）。现在，请你帮maze计算：他有多少种不同的修建土地的方案数？
（请你将方案数对12345678取模）
输入
输入第一行两个数字n,m。
接下来N行，每行M个字符，’.’表示普通格子，’X’表示蓄水池。
输出
仅一行，包含一个数字，为取模后的方案数。
一组输入输出大概长这样：
输入： 输出：
3 5 5851854
.X...
....X
X....
题意抽象：
给定一个n*m个格子矩形，现在要将1,2,3....n*m个数字填入格子。
问有且仅有指定格子满足条件p的方案数。
条件p：该格子中的数比邻近8个格子中的数都小。
数据范围1≤n≤4，m≤7。
首先数据范围挺小，最多28个格子，最多能不能有8个蓄水池。
于是想着搜一下。
但仔细想想发现还真是挺复杂的。
有几个关键点：
1.从小往大放数讨论方案数。这样的话如果“X”处已经放数了，那么它的旁边都可以放数了。否则它周围禁止放数。
2.不宜直接讨论当且仅当X处是蓄水池的方案数。讨论这样的方案数：保证题中所给的k个X处是蓄水池，但其他地方也可能是蓄水池的方案数。然后容斥。
这个容斥略有难想。
设目标状态S0中有k个蓄水池。设Ak为至少这k个X处是蓄水池的方案数。
先一次calc(S0)求出AS0。
然后要把其他地方还有蓄水池的方案数减掉。
于是往S0上加蓄水池(把某一个'.'变成‘X’），设加一个得到的状态S1.
由于加蓄水池的地方不同，会有很多种S1，我们记它们为S1,0...S1,i....S1,q
我们要减去的是AS1,0 ....AS1,i...AS1,q的并集的元素数目。
到这里容斥就很明显了。
更多具体细节在代码中注释：
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int mo=;
int n,m,ans,tp;
char graph[][];
bool use[][];
int f[<<][];
int ax[],ay[];
void Input()
{
scanf("%d%d\n",&n,&m);
rep(i,,n-)
{
scanf("%s",graph[i]);
}
ans=;
}
bool inrange(int x,int y)
{
return x>=&&y>=&&x<n&&y<m;
}
int calc()
{
tp=;
memset(f,,sizeof(f));
f[][]=;
rep(i,,n-)
{
rep(j,,m-)
{
if(graph[i][j]=='X')
{
ax[tp]=i;ay[tp]=j;tp++;
}
}
}
for(int s=;s<(<<tp);++s)
{
memset(use,,sizeof(use));
rep(i,,tp-)
{
if(!(s&(<<i))) //如果这个X还没有放数
rep(dx,-,)
{
rep(dy,-,)
{
if(inrange(ax[i]+dx,ay[i]+dy)) use[ax[i]+dx][ay[i]+dy]=;
}
}
}
int cnt=; //cnt为可以随便放的位置的个数
rep(i,,n-)
{
rep(j,,m-) if(use[i][j]) ++cnt;
}
rep(i,,cnt) //数是从小往大放，只有X位置上已经放数了之后周围才能放数
{
if(f[s][i])
{
f[s][i+]=(f[s][i+]+f[s][i]*(cnt-i))%mo; //往无影响区域放数
rep(j,,tp-)
{
if(!(s&(<<j)))
{
f[s|(<<j)][i+]=(f[s|(<<j)][i+]+f[s][i])%mo; //往X上放数
}
}
}
}
}
return f[(<<tp)-][n*m];
}
void go(int x,int y,int k)
{ if(x>=n) ans=(ans+k*calc())%mo;
else if(y>=m) go(x+,,k);
else
{
go(x,y+,k);
bool ok=;
rep(dx,-,)
{
rep(dy,-,)
{
if(inrange(x+dx,y+dy)&&graph[x+dx][y+dy]=='X') ok=;
}
}
if(ok) //如果ok为0，这个点不能再设蓄水池了（注意此时(x,y)处必定不为题中所给蓄水池位置之一）
{
graph[x][y]='X';
go(x,y+,-k); //容斥。一条go路径得到的答案是'X'都满足是蓄水池但'.'处也可能是蓄水池的方案数
graph[x][y]='.';
}
}
}
int solve()
{
rep(i,,n-)
{
rep(j,,m-)
{
// printf("i=%d j=%d %c\n",i,j,graph[i][j]);
if(graph[i][j]=='X')
rep(dx,-,)
{
rep(dy,-,)
{
if((dx||dy)&&inrange(i+dx,j+dy)&&graph[i+dx][j+dy]=='X') return ;
}
}
}
}
ans=;
go(,,);
ans=(ans+mo)%mo;
return ans;
}
int main()
{
// freopen("in.txt","r",stdin);
Input();
printf("%d\n",solve());
return ;
}