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容斥一下。
参考程序
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17 18 #define N 100008 19 #define M 50008 20 #define LL long long 21 #define lson l,m,rt<<1 22 #define rson m+1,r,rt<<1|1 23 #define clr(x,v) memset(x,v,sizeof(x)); 24 #define rep(x,y,z) for (int x=y;x<=z;x++) 25 #define repd(x,y,z) for (int x=y;x>=z;x--) 26 const int mo = 772002; 27 const int inf = 0x3f3f3f3f; 28 const int INF = 2000000000; 29 /**************************************************************************/ 30 int n,m,ans,dp[30][1024],w[1024],tx[10],ty[10]; 31 char mp[10][10]; 32 int flag[10][10]; 33 const int dx[9]={-1,-1,-1,0,0,0,1,1,1}; 34 const int dy[9]={-1,0,1,-1,0,1,-1,0,1}; 35 void up(int &x,int y){ 36 x = (x + y) % mo; 37 if (x>=mo) x-=mo; 38 } 39 int solve(){ 40 int cnt=0; 41 rep(i,1,n) rep(j,1,m) 42 if (mp[i][j]=='X'){ 43 tx[++cnt]=i; 44 ty[cnt]=j; 45 } 46 for (int i=0;i<1<<cnt;i++){ 47 clr(flag,0); 48 for (int j=1;j<=cnt;j++) 49 if (i & 1<<j-1) 50 for (int k=0;k<9;k++) flag[tx[j]+dx[k]][ty[j]+dy[k]]=1; 51 w[i]=0; 52 rep(j,1,n) rep(k,1,m) 53 if (!flag[j][k]) w[i]++; 54 } 55 clr(dp,0); 56 dp[0][0]=1; 57 for (int i=1;i<=n*m;i++) 58 for (int j=0;j<1<<cnt;j++) 59 { 60 for (int k=1;k<=cnt;k++) 61 if (j & 1<<k-1) 62 up(dp[i][j],dp[i-1][j - (1<<k-1)]); 63 up(dp[i][j],dp[i-1][j]*(w[j]-i+1)); 64 } 65 return dp[n*m][(1<<cnt)-1]; 66 } 67 void dfs(int x,int y,int p){ 68 if (y==m+1){ 69 x++; 70 y=1; 71 } 72 if (x==n+1){ 73 ans=(ans + solve()*p) % mo; 74 if (ans<0) ans+=mo; 75 return; 76 } 77 int flag=0; 78 for (int i=0;i<9;i++) if (i!=4&&mp[x+dx[i]][y+dy[i]]=='X') flag=1; 79 if (mp[x][y]=='X') 80 if (flag) return; else dfs(x,y+1,p); 81 else 82 { 83 dfs(x,y+1,p); 84 if (!flag) 85 { 86 mp[x][y]='X'; 87 dfs(x,y+1,-p); 88 mp[x][y]='.'; 89 } 90 } 91 } 92 int main(){ 93 int cas=0; 94 while (~scanf("%d %d",&n,&m)){ 95 clr(mp,0); ans=0; 96 rep(i,1,n) scanf("%s",mp[i]+1); 97 dfs(1,1,1); 98 printf("Case #%d: %d ",++cas,ans); 99 } 100 }