Description
对于一个n*m的地图，每个格子有五种可能：平地，障碍物，出口，入口和神器。一个有效的地图必须满足下列条件：
1.入口，出口和神器都有且仅出现一次，并且不在同一个格子内。
2.入口，出口和神器两两都是连通的。
连通性判断为四连通。
现在给出一个n*m的地图，其中一些格子的状态已经确定，另一些格子的状态未确定。
问当所有的格子状态确定之后，有多少种情况使得该地图是一个有效的地图？输出结构为答案模1e9+7。
Input
第一行输入两个整数n和m，意义如题目所示。接下来n行，每行m个字符：
字符'.'表示平地
字符'#'表示障碍物
字符'?'表示未确定
字符'S'表示入口
字符'X'表示神器
字符'E'表示出口
Output
一行，表示方案数
Sample Input
2 3
S#E
???
Sample Output
3
HINT
对于30%的数据，？数量小于10
对于100%的数据，1<=n<=7，1<=m<=7
Solution
这是一道类插头DP的题目，做法与插头DP类似。
对于'?'，我们可以枚举情况；而对于其他已经确定了的状态，可以直接按格DP。
状态只需记录格子所在的连通块，并在最后记录入口，出口和神器所在的连通块，HASH存。
Code
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm> using namespace std; #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define DWN(i, a, b) for (int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define mset(a, b) memset(a, b, sizeof(a))
typedef long long LL;
const int MAXD = , HASH = , STATE = , MOD = 1e9+;
int n, m, code[MAXD], ch[MAXD], x[], y[];
char maze[MAXD][MAXD], sp[] = {'S', 'X', 'E', '.', '#'}; void add(LL &x, LL y) { x += y; if (x >= MOD) x -= MOD; } struct HASHMAP
{
int head[HASH], nxt[STATE], siz; LL state[STATE], f[STATE];
void clear() { siz = , mset(head, -); }
void push(LL x, LL k)
{
int pos = x%HASH, i = head[pos];
for (; i != -; i = nxt[i])
if (state[i] == x) { add(f[i], k); return ; }
state[siz] = x, f[siz] = k;
nxt[siz] = head[pos], head[pos] = siz++;
}
}hm[]; void in()
{
scanf("%d %d", &n, &m);
mset(x, -), mset(y, -);
REP(i, , n)
{
scanf("%s", maze[i]+);
REP(j, , m)
{
if (maze[i][j] == 'S') x[] = i, y[] = j;
else if (maze[i][j] == 'X') x[] = i, y[] = j;
else if (maze[i][j] == 'E') x[] = i, y[] = j;
}
}
} bool check(int i, int j)
{
if (maze[i][j] == 'S' && code[m+]) return ;
else if (maze[i][j] == 'X' && code[m+]) return ;
else if (maze[i][j] == 'E' && code[m+]) return ;
else return ;
} void decode(LL x)
{
REP(i, , m+) code[i] = x&, x >>= ;
} LL encode(int i, int j)
{
if (maze[i][j] == 'S') code[m+] = code[j];
else if (maze[i][j] == 'X') code[m+] = code[j];
else if (maze[i][j] == 'E') code[m+] = code[j];
LL ret = ; int cnt = ;
mset(ch, -), ch[] = ;
DWN(t, m+, )
{
if (ch[code[t]] == -) ch[code[t]] = ++cnt;
ret <<= , ret |= ch[code[t]];
}
return ret;
} void dp_blank(int i, int j, int cur)
{
REP(k, , hm[cur].siz-)
{
decode(hm[cur].state[k]);
if (check(i, j)) continue ;
int lef = code[j-], up = code[j], id = ;
if (lef) id = min(id, lef);
if (up) id = min(id, up);
if (lef)
REP(t, , m+) if (code[t] == lef) code[t] = id;
if (up)
REP(t, , m+) if (code[t] == up) code[t] = id;
code[j] = id;
hm[cur^].push(encode(i, j), hm[cur].f[k]);
}
} void dp_block(int i, int j, int cur)
{
REP(k, , hm[cur].siz-)
{
decode(hm[cur].state[k]), code[j] = ;
hm[cur^].push(encode(i, j), hm[cur].f[k]);
}
} void work()
{
int cur = ; LL ans = ;
hm[].clear(), hm[].clear(), hm[].push(, );
REP(i, , n)
REP(j, , m)
{
if (maze[i][j] != '?')
{
if (maze[i][j] == '#') dp_block(i, j, cur);
else dp_blank(i, j, cur);
}
else
{
REP(t, , )
{
if (t < && x[t] != -) continue ;
maze[i][j] = sp[t];
if (maze[i][j] == '#') dp_block(i, j, cur);
else dp_blank(i, j, cur);
}
}
hm[cur].clear(), cur ^= ;
}
REP(i, , hm[cur].siz-)
{
decode(hm[cur].state[i]);
if ((!code[m+]) || (!code[m+]) || (!code[m+])) continue ;
int t = code[m+];
if (code[m+] != t || code[m+] != t) continue ;
add(ans, hm[cur].f[i]);
}
printf("%I64d\n", ans);
} int main()
{
in();
work();
return ;
}