【题目大意】
给定一个M*N的矩阵，问从左下角经过所有非障碍点到达右下角有多少种方案？
【算法分析】
我们先把图改一下。
比如说样例
..
..
那么改成
……
.####.
.#..#.
......
这样转化以后，就变成求哈密顿回路的方案数了。
因为最外面那一圈必须走。
于是用Cdq的论文的方法解决。
【其它】1A，hash开到10003是47MS,开到473 是32MS。。。果然我的怎么说都比较慢啊。。。
【CODE】
#include #include #include #include #define cf(x) (1<<(x))
using namespace std;
const int key=473;
const int INF=0x7FFFFFFF;
typedef long long LL;
struct gtp{int y,next;}g[200000];
int m,n,ng,pg,e,mx,my;
char c[15][15];
LL fl[2][200000],ans;
int sl[2][200000];
int tot[2],ls[key];
inline void init(){e=0;memset(ls,0,sizeof(ls));}
inline void addedge(int x,int y){e++; g[e].y=y; g[e].next=ls[x]; ls[x]=e;}
inline int ChaTou(int t1,int t2){
if (!t1 && !t2) return 0;
if (t1) return 1;
return 2;
}
void add(int s,LL f){
int st=s; if (st>=key) st%=key;
for (int t=ls[st];t;t=g[t].next)
if (sl[ng][g[t].y]==s){
fl[ng][g[t].y]+=f;
return;
}
sl[ng][++tot[ng]]=s;
fl[ng][tot[ng]]=f;
addedge(st,tot[ng]);
}
bool input(){
ng=1; pg=0; ans=0; tot[0]=0; tot[1]=0;
scanf("%d%d",&m,&n);
if (!m && !n) return false;
int i,j;
char ch;
memset(c,’#’,sizeof(c));
for (i=0;i for (j=0;j for (ch=getchar();ch!=’#’&&ch!=’.’;ch=getchar());
c[i+2][j+2]=ch;
}
m+=2; n+=4;
for (j=0;j for (i=0;i for (i=0;i c[m-1][1]=’.’; c[m-1][n-2]=’.’;
init();
add(1+cf((n<<1)+1),1);
mx=0; my=0;
for (i=0;i for (j=0;j if (c[i][j]==’.’){
mx=i;
my=j;
}
return true;
}
void No(int j){
int k,t1,t2;
for (k=1;k<=tot[pg];k++){
int &s=sl[pg][k];
if ((s&cf((j<<1)))||(s&cf((j<<1)+1))||(cf((n<<1))&s)||(cf((n<<1)+1)&s)) continue;
add(s,fl[pg][k]);
}
}
void Yes(int I,int j){
int k,lct,uct,ts,i,top,ct;
for (k=1;k<=tot[pg];k++){
int &s=sl[pg][k];
LL &f=fl[pg][k];
uct=ChaTou(s&cf((j<<1)),s&cf((j<<1)+1));
lct=ChaTou(s&cf((n<<1)),s&cf((n<<1)+1));
if (!j && lct) continue;
ts=(INF-cf((j<<1))-cf((j<<1)+1)-cf((n<<1))-cf((n<<1)+1))&s;
switch (lct){
case 0:
switch (uct){
case 0:
add(ts|cf((j<<1))|cf((n<<1)+1),f);
break;
case 1:
add(ts|cf((j<<1)),f);
add(ts|cf((n<<1)),f);
break;
case 2:
add(ts|cf((j<<1)+1),f);
add(ts|cf((n<<1)+1),f);
break;
}
break;
case 1:
switch (uct){
case 0:
add(ts|cf((j<<1)),f);
add(ts|cf((n<<1)),f);
break;
case 1:
top=0;
for (i=j;;i++){
ct=ChaTou(s&cf((i<<1)),s&cf((i<<1)+1));
if (ct==1) top++;
if (ct==2) top–;
if (top==0) break;
}
add((ts^cf((i<<1)+1))|cf((i<<1)),f);
break;
case 2:
if (I==mx && j==my && ts==0) ans+=f;
break;
}
break;
case 2:
switch (uct){
case 0:
add(ts|cf((j<<1)+1),f);
add(ts|cf((n<<1)+1),f);
break;
case 1:
add(ts,f);
break;
case 2:
top=0;
for (i=j;;i–){
ct=ChaTou(s&cf((i<<1)),s&cf((i<<1)+1));
if (ct==1) top++;
if (ct==2) top–;
if (top==0) break;
}
add((ts^cf((i<<1)))|cf((i<<1)+1),f);
break;
}
break;
}
}
}
void dp(){
for (int i=0;i for (int j=0;j if (!i && !j) continue;
ng=1-ng;
pg=1-pg;
tot[ng]=0;
init();
if (c[i][j]==’#’) No(j);
else Yes(i,j);
}
}
int main(){
while (input()){
dp();
cout << ans << endl;
}
return 0;
}