假设我们当前已经填充成如图所示的情况：需要填写（i，j）这个格子了
那么：我们有两个大类，六种情况~~~
第一类：
（i，j）格子本身是个障碍点，不可达
第一类：
（i，j）格子本身是个障碍点，不可达
那么，应该是如图：
当左插头和上插头都不存在的时候，那么才是合法的状态，可以状态转移
第二类：
（i，j）可达
第一种情况：
左插头和上插头都存在，且ID号不同：说明需要合并连通分量（ID号相同合并也没有啥意义）
ID号相同且到达最后一个节点：
计算终态
第二种情况：
当只有左插头，没有上插头时候，我们可以发现，插头可以往右边走，也可以往下边走
同理，当只有上插头时，插头可以右走，也可以下走
这样，出现了四种状态转移
第三种情况：
当左右插头都没有时，因为这个点必须在回路上，所以要新生成一个连通分量，也是一种状态转移~~~
对着网上题解敲了两种~~~
第一种的注释配上图片应该还是蛮好理解的~（自我感觉良好）
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
const int STATE = 1000000 + 10;
const int HASH = 30007;
const int MAXD = 15;
int N,M;
int ex,ey;
int cur;
int mp[MAXD][MAXD];
ll sum;
struct HASHMAP{
int Size,Head[HASH],Next[STATE];
long long state[STATE];
long long f[STATE];
void init(){
memset(Head,-1,sizeof(Head));
Size=0;
}
void push(ll st,ll num){
ll h = st % HASH;
for(int i=Head[h];i!=-1;i=Next[i])
if (state[i]==st){
f[i]+=num;
return;
}
Next[Size]=Head[h];
Head[h]=Size;
f[Size]=num;
state[Size]=st;
Size++;
}
}hm[2];
void decode(int *code,ll st){
for(int i=M;i>=0;i--){
code[i]=st&7;
st>>=3;
}
}
ll encode(int *code){
int ch[MAXD];
memset(ch,-1,sizeof(ch));
ch[0]=0;
int cnt=1;
ll st=0;
for(int i=0;i<=M;i++){
if (ch[code[i]]==-1) ch[code[i]]=cnt++;
code[i]=ch[code[i]];
st<<=3;
st|=code[i];
}
return st;
}
void shift(int *code){
for(int i=M;i>=1;i--)
code[i]=code[i-1];
code[0]=0;
}
//当前格子为障碍格子
void dpblock(int i,int j){
for(int k=0;k<hm[cur].Size;k++){
ll st=hm[cur].state[k];
int code[MAXD];
decode(code,st);
int Left=code[j-1],Up=code[j];
//没有插头，才能生成新状态
//否则是非法状态
if (Left==0 && Up==0){
if (j==M) shift(code);
hm[1-cur].push(encode(code),hm[cur].f[k]);
}
}
}
void dpblank(int i,int j){
for(int k=0;k<hm[cur].Size;k++){
ll st=hm[cur].state[k];
ll num=hm[cur].f[k];
int code[MAXD];
decode(code,st);
int Left=code[j-1],Up=code[j];
if (Left>0 && Up>0){
if (Left != Up){
code[j-1] = code[j] = 0;
for(int l=0;l<=M;l++)
if (code[l]==Up)
code[l]=Left;
if (j==M) shift(code);
hm[1-cur].push(encode(code),num);
}
//左插头和上插头相遇
//到达终点了，(ex,ey)标记的是最后一个非可达格子
else if (i==ex && j==ey){
sum += num;
code[j-1] = code[j] = 0;
if (j==M) shift(code);
hm[1-cur].push(encode(code),num);
}
}
//左插头和下插头存在某一个
//上面的情况已经判断了两个都存在的情况，所以这里不可能存在两个
else if (Left > 0 || Up > 0){
//(i,j)的右边可达，是个可达格子
if (mp[i][j+1]){
code[j-1]=0;
//这里写的是加，因为有一个是0，所以表达的是延续这个插头状态
code[j]=Left + Up;
if (j==M) shift(code);
hm[1-cur].push(encode(code),num);
}
if (mp[i+1][j]){
code[j-1]=Left + Up;
code[j]=0;
if (j==M) shift(code);
hm[1-cur].push(encode(code),num);
}
}
else{
//(i,j)格子没有左插头和上插头
//(i,j)的下面和右边都是可达格子
//否则，(i,j)不在回路中
if (mp[i][j+1] && mp[i+1][j]){
int maxc=1;
for(int l=0;l<=M;l++)
maxc=max(maxc,code[l]);
//新建一个连通分量
code[j-1]=code[j]=maxc+1;
hm[1-cur].push(encode(code),num);
}
}
}
}
void init(){
char a;
ex=ey=0;
memset(mp,0,sizeof(mp));
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
scanf("%c",&a);
if (a=='.'){
mp[i][j]=1;
ex=i;
ey=j;
}
}
getchar();
}
}
void solve(){
sum=0;
cur=0;
hm[cur].init();
hm[cur].push(0,1);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
hm[1-cur].init();
if (mp[i][j])
dpblank(i,j);
else
dpblock(i,j);
cur=1-cur;
}
//printf("%I64d\n",sum);
printf("%lld\n",sum);
}
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&N,&M)!=EOF){
getchar();
init();
if (ex==0){
puts("0");
continue;
}
solve();
}
return 0;
}
第二种写法来自我bin神的博客：
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXD = 15;
const int HASH = 30007;
const int STATE = 1000000 + 10;
int N,M;
int mp[MAXD][MAXD];
int code[MAXD];
int ch[MAXD];
int ex,ey;
#define ll long long
struct HASHMAP{
int Head[HASH],Next[HASH],Size;
ll state[STATE];
ll f[STATE];
void init(){
Size = 0;
memset(Head,-1,sizeof(Head));
}
void push(ll st,ll ans){
int h=st%HASH;
for(int i=Head[h];i!=-1;i=Next[i])
if (state[i] == st){
f[i] += ans;
return;
}
state[Size]=st;
f[Size]=ans;
Next[Size]=Head[h];
Head[h]=Size++;
}
}hm[2];
void decode(int *code,int m,ll st){
for(int i=m;i>=0;i--){
code[i]=st&7;
st>>=3;
}
}
ll encode(int *code,int m){
int cnt=1;
memset(ch,-1,sizeof(ch));
ch[0]=0;
ll st=0;
for(int i=0;i<=m;i++){
if (ch[code[i]]==-1) ch[code[i]]=cnt++;
code[i]=ch[code[i]];
st<<=3;
st|=code[i];
}
return st;
}
void shift(int *code,int m){
for(int i=m;i>0;i--)
code[i]=code[i-1];
code[0]=0;
}
void dpblank(int i,int j,int cur){
int Up,Left;
for(int k=0;k<hm[cur].Size;k++){
decode(code,M,hm[cur].state[k]);
Left=code[j-1];
Up=code[j];
if (Left && Up){
if (Left == Up){
if (i==ex && j==ey){
code[j-1] = code[j] = 0;
if (j==M) shift(code,M);
hm[cur^1].push(encode(code,M),hm[cur].f[k]);
}
}
else{
code[j-1] = code[j] = 0;
for(int t=0; t<=M; t++)
if (code[t] == Up)
code[t] = Left;
if (j==M) shift(code,M);
hm[cur^1].push(encode(code,M),hm[cur].f[k]);
}
}
else if (Left + Up > 0){
if (mp[i][j+1]){
code[j-1]=0;
code[j]=Left + Up;
hm[cur^1].push(encode(code,M),hm[cur].f[k]);
}
if (mp[i+1][j]){
code[j-1]=Left + Up;
code[j]=0;
if (j==M) shift(code,M);
hm[cur^1].push(encode(code,M),hm[cur].f[k]);
}
}
else{
if (mp[i][j+1] && mp[i+1][j]){
int maxc=1;
for(int t=0;t<=M;t++)
maxc=max(maxc,code[t]);
code[j-1]=code[j]=maxc+1;
hm[cur^1].push(encode(code,M),hm[cur].f[k]);
}
}
}
}
void dpblock(int i,int j,int cur){
for(int k=0;k<hm[cur].Size;k++){
decode(code,M,hm[cur].state[k]);
if (code[j-1]==0 && code[j]==0){
if (j==M) shift(code,M);
hm[cur^1].push(encode(code,M),hm[cur].f[k]);
}
}
}
char str[MAXD];
void init(){
memset(mp,0,sizeof(mp));
ex=0;
for(int i=1;i<=N;i++){
scanf("%s",str);
for(int j=0;j<M;j++)
if (str[j]=='.'){
ex=i;
ey=j+1;
mp[i][j+1]=1;
}
}
}
void solve(){
int cur=0;
ll ans=0;
hm[cur].init();
hm[cur].push(0,1);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++){
hm[cur^1].init();
if (mp[i][j])
dpblank(i,j,cur);
else
dpblock(i,j,cur);
cur^=1;
}
for(int i=0;i<hm[cur].Size;i++)
ans+=hm[cur].f[i];
printf("%lld\n",ans);
}
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&N,&M)!=EOF){
init();
if (ex==0){
puts("0");
continue;
}
solve();
}
return 0;
}
京公网安备 11010502036488号