楼教主男人八题之一。。。
题目大意：
求从左下角经过所有非障碍点一次到达右下角的方案数
这里不是求回路，但是我们可以考虑，在最下面一行再增加一行，那么就可以当做求此时左下角到右下角的回路总数，那么就转化成了陈丹琦论文的URAL1519的
方法了
但是最后一行添加的格子必须是最后一条直线跑的，也就是除了左下角和右下角中间的点只能有水平方向上的插头
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std;
#define ll long long
const int HASH = ;
const int STATE = ;
const int MAXD = ;
int n , m , enx , eny;
int code[MAXD] , mp[MAXD][MAXD];
bool flag[MAXD][MAXD];//标记位，标记当前点能否作为最终点
ll ans = ;
struct HASHMAP{
int head[HASH] , next[STATE] , state[STATE] , size;
ll f[STATE]; void init(){
size = ;
memset(head , - , sizeof(head));
} void push_in(int st , ll sum){
int h = st%HASH;
for(int i = head[h] ; ~i ; i=next[i]){
if(st == state[i]){
f[i]+=sum;
return ;
}
}
f[size]=sum;
state[size] = st;
next[size] = head[h];
head[h] = size++;
}
}hashmap[]; int num = ;//记录共有的插头数量
void decode(int *code , int m , int st)
{
num = ;
for(int i=m ; i>= ; i--){
code[i] = st&;
st>>=;
if(code[i]) num++;
}
} int encode(int *code , int m)
{
int st=;
for(int i= ; i<=m ; i++){
st<<=;
st |= code[i];
}
return st;
} void shift(int *code , int m) //换行,可理解为将最右侧轮廓线换到了下一行的最左侧
{
for(int i=m ; i>= ; i--) code[i] = code[i-];
code[] = ;
} void dpblank(int i , int j , int cur)
{
int k , left , up;
for(k= ; k<hashmap[cur].size ; k++){
decode(code , m , hashmap[cur].state[k]);
left = code[j-];
up = code[j];
// cout<<"chatou: "<<i<<" "<<j<<" "<<left<<" "<<up<<endl;
if(!left && !up){
if(mp[i][j+] && mp[i-][j]){ //不断向上转移
code[j-] = , code[j] = ;
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
}
else if(!left && up){
if(mp[i][j+]) hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
if(mp[i-][j]){
code[j-] = up , code[j] = ;
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
}
else if(left && !up){
if(mp[i-][j]){
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
if(mp[i][j+]){
code[j-] = , code[j] = left;
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
}
else if(left== && up == ){
int cnt = ;
for(int v=j+ ; v<=m ; v++){
if(code[v]==)cnt++;
if(code[v]==)cnt--;
if(!cnt){
code[v]=;
break;
}
}
code[j-] = code[j] = ;
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
else if(left == && up == ){
int cnt=;
for(int v=j- ; v>= ; v--){
if(code[v]==)cnt++;
if(code[v]==)cnt--;
if(!cnt){
code[v]=;
break;
}
}
code[j-] = code[j] = ;
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
else if(left== && up==){
if(i==enx && j==eny) {
code[j-] = code[j] = ;
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
}
else{
code[j-]=code[j]=;
if(j == m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
}
} void dpblock(int i , int j , int cur)
{
int k , left , up;
for(k= ; k<hashmap[cur].size ; k++){
decode(code , m , hashmap[cur].state[k]);
left = code[j-];
up = code[j];
// cout<<"block: "<<i<<" "<<j<<" "<<left<<" "<<up<<endl;
if(!left && !up){
if(j==m) shift(code , m);
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]); }
}
} void dpselect(int i , int j , int cur)
{
int k , left , up;
for(k= ; k<hashmap[cur].size ; k++){
decode(code , m , hashmap[cur].state[k]);
left = code[j-];
up = code[j];
if(left== && !up){
code[j-] = , code[j] = ;
hashmap[cur^].push_in(encode(code , m) , hashmap[cur].f[k]);
}
}
} char s[MAXD][MAXD]; void init()
{
for(int i= ; i<=n ; i++){
scanf("%s" , s[i]+);
for(int j= ; j<=m ; j++){
mp[i][j] = s[i][j]=='.';
}
}
for(int i=n ; i>= ; i--)
for(int j= ; j<=m ; j++)
if(mp[i][j]) enx=i , eny=j;
mp[n+][] = , mp[n+][m] = ;
for(int i= ; i<m ; i++) mp[n+][i] = ;
n++;
for(int i= ; i<=m+ ; i++) mp[][i] = ;
for(int i= ; i<=n ; i++) mp[i][m+] = ;
/* for(int i=0 ; i<=n ; i++)
{
for(int j=1 ; j<=m+1 ; j++){
cout<<mp[i][j]<<" ";
}
cout<<endl;
}
cout<<enx<<" "<<eny<<endl;*/
} ll solve()
{
ans = ;
int cur = ;
hashmap[cur].init();
hashmap[cur].push_in( , );
for(int i=n ; i>= ; i--){
for(int j= ; j<=m ; j++){
hashmap[cur^].init();
if(mp[i][j]==) dpblank(i , j , cur);
else if(mp[i][j]==) dpblock(i , j , cur);
else dpselect(i , j , cur);
cur^=;
} }
for(int i= ; i<hashmap[cur].size ; i++) ans+=hashmap[cur].f[i];
return ans;
} int main()
{
// freopen("in.txt" , "r" , stdin);
int cas = ;
while(scanf("%d%d" , &n , &m) , n+m)
{
init();
// printf("Case %d: ",++cas);
if(n== && m==){
printf("%d\n" , );
continue;
}
printf("%I64d\n" , solve());
}
return ;
}