Problem Mountain
题目大意
给定一张n*m的地图，由 . 和 X 组成。要求给每个点一个1~n*m的数字（每个点不同），使得编号为X的点小于其周围的点，编号为.的点至少大于一个其周围的点。
n<=5 , m<=5。
解题分析
考虑从1~n*m，从小到大依次填数，则如果某个位置编号为X且该位置还未填数，那么其周围的点均不能填数。
令dp[i][j]表示填到第i个数，状态为j 。 令X的个数为cnt，那么 j ∈[ 0 , 1<<cnt)。
一种情况为第i个数填在 X 的位置上，那么dp[i][j] 可以由 dp[i-1][j-{x}] 转移过来。 j - {x} 表示去掉某个X后的状态。
另一种情况为第i个数填在 . 的位置，那么首先预处理一下w[j]表示状态为j时有多少个位置是可以填的，那么dp[i]][j] += dp[i-1][j] * (w[j] - (i-1))
又因为要保证遍号为.的点至少大于一个其周围的点，dfs容斥一下。
参考程序
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std; #define N 100008
#define M 50008
#define LL long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define clr(x,v) memset(x,v,sizeof(x));
#define rep(x,y,z) for (int x=y;x<=z;x++)
#define repd(x,y,z) for (int x=y;x>=z;x--)
const int mo = ;
const int inf = 0x3f3f3f3f;
const int INF = ;
/**************************************************************************/
int n,m,ans,dp[][],w[],tx[],ty[];
char mp[][];
int flag[][];
const int dx[]={-,-,-,,,,,,};
const int dy[]={-,,,-,,,-,,};
void up(int &x,int y){
x = (x + y) % mo;
if (x>=mo) x-=mo;
}
int solve(){
int cnt=;
rep(i,,n) rep(j,,m)
if (mp[i][j]=='X'){
tx[++cnt]=i;
ty[cnt]=j;
}
for (int i=;i<<<cnt;i++){
clr(flag,);
for (int j=;j<=cnt;j++)
if (i & <<j-)
for (int k=;k<;k++) flag[tx[j]+dx[k]][ty[j]+dy[k]]=;
w[i]=;
rep(j,,n) rep(k,,m)
if (!flag[j][k]) w[i]++;
}
clr(dp,);
dp[][]=;
for (int i=;i<=n*m;i++)
for (int j=;j<<<cnt;j++)
{
for (int k=;k<=cnt;k++)
if (j & <<k-)
up(dp[i][j],dp[i-][j - (<<k-)]);
up(dp[i][j],dp[i-][j]*(w[j]-i+));
}
return dp[n*m][(<<cnt)-];
}
void dfs(int x,int y,int p){
if (y==m+){
x++;
y=;
}
if (x==n+){
ans=(ans + solve()*p) % mo;
if (ans<) ans+=mo;
return;
}
int flag=;
for (int i=;i<;i++) if (i!=&&mp[x+dx[i]][y+dy[i]]=='X') flag=;
if (mp[x][y]=='X')
if (flag) return; else dfs(x,y+,p);
else
{
dfs(x,y+,p);
if (!flag)
{
mp[x][y]='X';
dfs(x,y+,-p);
mp[x][y]='.';
}
}
}
int main(){
int cas=;
while (~scanf("%d %d",&n,&m)){
clr(mp,); ans=;
rep(i,,n) scanf("%s",mp[i]+);
dfs(,,);
printf("Case #%d: %d\n",++cas,ans);
}
}