（题目来自洛谷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=12345678; int n,m,ans,tp; char graph[10][10]; bool use[10][10]; int f[1<<9][50]; int ax[20],ay[20]; void Input() { scanf("%d%d ",&n,&m); rep(i,0,n-1) { scanf("%s",graph[i]); } ans=0; } bool inrange(int x,int y) { return x>=0&&y>=0&&x<n&&y<m; } int calc() { tp=0; memset(f,0,sizeof(f)); f[0][0]=1; rep(i,0,n-1) { rep(j,0,m-1) { if(graph[i][j]=='X') { ax[tp]=i;ay[tp]=j;tp++; } } } for(int s=0;s<(1<<tp);++s) { memset(use,1,sizeof(use)); rep(i,0,tp-1) { if(!(s&(1<<i))) //如果这个X还没有放数 rep(dx,-1,1) { rep(dy,-1,1) { if(inrange(ax[i]+dx,ay[i]+dy)) use[ax[i]+dx][ay[i]+dy]=0; } } } int cnt=0; //cnt为可以随便放的位置的个数 rep(i,0,n-1) { rep(j,0,m-1) if(use[i][j]) ++cnt; } rep(i,0,cnt) //数是从小往大放，只有X位置上已经放数了之后周围才能放数 { if(f[s][i]) { f[s][i+1]=(f[s][i+1]+f[s][i]*(cnt-i))%mo; //往无影响区域放数 rep(j,0,tp-1) { if(!(s&(1<<j))) { f[s|(1<<j)][i+1]=(f[s|(1<<j)][i+1]+f[s][i])%mo; //往X上放数 } } } } } return f[(1<<tp)-1][n*m]; } void go(int x,int y,int k) { if(x>=n) ans=(ans+k*calc())%mo; else if(y>=m) go(x+1,0,k); else { go(x,y+1,k); bool ok=1; rep(dx,-1,1) { rep(dy,-1,1) { if(inrange(x+dx,y+dy)&&graph[x+dx][y+dy]=='X') ok=0; } } if(ok) //如果ok为0，这个点不能再设蓄水池了（注意此时(x,y)处必定不为题中所给蓄水池位置之一） { graph[x][y]='X'; go(x,y+1,-k); //容斥。一条go路径得到的答案是'X'都满足是蓄水池但'.'处也可能是蓄水池的方案数 graph[x][y]='.'; } } } int solve() { rep(i,0,n-1) { rep(j,0,m-1) { // printf("i=%d j=%d %c ",i,j,graph[i][j]); if(graph[i][j]=='X') rep(dx,-1,1) { rep(dy,-1,1) { if((dx||dy)&&inrange(i+dx,j+dy)&&graph[i+dx][j+dy]=='X') return 0; } } } } ans=0; go(0,0,1); ans=(ans+mo)%mo; return ans; } int main() { // freopen("in.txt","r",stdin); Input(); printf("%d ",solve()); return 0; }