Tony's tour(poj1739,男人题之一，插头dp）

Tony's Tour

Time Limit: 1000MS		Memory Limit: 30000K

Description

A square township has been divided up into n*m(n rows and m columns) square plots (1<=N,M<=8),some of them are blocked, others are unblocked. The Farm is located in the lower left plot and the Market is located in the lower right plot. Tony takes her tour of the township going from Farm to Market by walking through every unblocked plot exactly once.
Write a program that will count how many unique tours Betsy can take in going from Farm to Market.

Input

The input contains several test cases. The first line of each test case contain two integer numbers n,m, denoting the number of rows and columns of the farm. The following n lines each contains m characters, describe the farm. A '#' means a blocked square, a '.' means a unblocked square.
The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

2 2
..
..
2 3
#..
...
3 4
....
....
....
0 0

Sample Output

1
1
4

Source

LouTiancheng@POJ

WA了好长时间。。不知道是orz谁的代码。。写完了发现和他写的一模一样。。我WA的原因是cur是全局的。。

Codes:

  1 #include<set>
  2 #include<queue>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<iostream>
  6 #include<algorithm>
  7 using namespace std;
  8 const int N = 50003;
  9 const int Mod = 10007;
 10 #define nxt (cur^1)
 11 #define For(i,n) for(int i=1;i<=n;i++)
 12 #define Rep(i,l,r) for(int i=l;i<=r;i++)
 13 #define Down(i,r,l) for(int i=r;i>=l;i--)
 14 struct statedp{
 15     int state[N],size,head[Mod],next[N];
 16     long long f[N];
 17     void clear(){size=0;memset(head,-1,sizeof(head));}
 18     void push(int st,long long ans){
 19         int Key = st % Mod;
 20         for(int p = head[Key];p!=-1;p=next[p])
 21             if(state[p]==st){
 22                 f[p]+=ans;
 23                 return;    
 24             }
 25         state[size] = st;f[size]=ans;
 26         next[size]=head[Key];head[Key]=size++;
 27     }
 28 }dp[2];
 29 long long ans;
 30 int cur,n,m,maze[15][15],code[15];
 31 char ch;
 32 
 33 void init(){
 34     memset(maze,0,sizeof(maze));
 35     For(i,n){
 36         scanf("
");
 37         For(j,m){
 38             scanf("%c",&ch);
 39             if(ch=='#') maze[i][j] = 1;
 40             else        maze[i][j] = 0;
 41         }
 42     }
 43 }
 44 
 45 int encode(){
 46     int ret = 0;
 47     Rep(i,0,m) ret = ret << 2 | code[i];
 48     return ret;
 49 }
 50 
 51 void decode(int st){
 52     Down(i,m,0) code[i] = st&3 , st>>=2;
 53 }
 54 
 55 void shift(){
 56     Down(i,m,1) code[i] = code[i-1]; code[0] = 0;
 57 }
 58 
 59 void dpblock(int i,int j,int cur){
 60     int Lim = (j==m)?(2):(0);
 61     int quick = (1<<(2*(m+1)-Lim)) - 1;
 62     Rep(k,0,dp[cur].size-1)
 63         dp[nxt].push((dp[cur].state[k]>>Lim)&quick,dp[cur].f[k]);
 64 }
 65 
 66 void dpblank(int i,int j,int cur){
 67     Rep(k,0,dp[cur].size-1){
 68         decode(dp[cur].state[k]);
 69         int Left = code[j-1] , Up = code[j];
 70         if(i==n&&j==1){
 71             if(Up){
 72                 code[j] = 0;
 73                 dp[nxt].push(encode(),dp[cur].f[k]);
 74             }
 75             else{
 76                 code[j] = 2;
 77                 dp[nxt].push(encode(),dp[cur].f[k]);
 78             }
 79             continue;
 80         }
 81         if(i==n&&j==m){
 82             if((Left||Up) && !(Left&&Up)) ans+=dp[cur].f[k];
 83             continue;
 84         }
 85         if(Left&&Up){
 86             if(Left==2&&Up==1) continue;
 87             if(Left==2&&Up==2){
 88                 code[j-1] = code[j] = 0;int KH = 1;
 89                 Rep(kh,j+1,m){
 90                     if(code[kh]==2) KH++;
 91                     if(code[kh]==1) KH--;
 92                     if(!KH) {code[kh] = 3 - code[kh];break;};
 93                 }
 94             }
 95             else if(Left==1&&Up==1){
 96                 code[j-1] = code[j] = 0;int KH = 1;
 97                 Down(kh,j-2,0){
 98                     if(code[kh]==2) KH--;
 99                     if(code[kh]==1) KH++;
100                     if(!KH) {code[kh] = 3 - code[kh];break;}
101                 }
102             }
103             else code[j-1] = code[j] = 0;
104             if(j==m) shift();
105             dp[nxt].push(encode(),dp[cur].f[k]);
106         }
107         else if(Left||Up){
108             int CODE = Left | Up;
109             if((i<n) && (!maze[i+1][j])){
110                 code[j-1] = CODE;code[j] = 0;
111                 if(j==m) shift();
112                 dp[nxt].push(encode(),dp[cur].f[k]);
113             }
114             if((j<m) && (!maze[i][j+1])){
115                 code[j] = CODE; code[j-1] = 0;
116                 dp[nxt].push(encode(),dp[cur].f[k]);
117             }
118         }
119         else if((!maze[i+1][j]) && (!maze[i][j+1]) && (i<n) && (j<m)){
120             code[j-1] = 2; code[j] = 1;
121             dp[nxt].push(encode(),dp[cur].f[k]);
122         }
123     }
124 }
125 
126 void DP(){
127     int cur = 0;
128     dp[0].clear();dp[0].push(0,1);ans = 0;
129     For(i,n)
130       For(j,m){
131           dp[nxt].clear();
132           if(maze[i][j])  dpblock(i,j,cur);
133           else            dpblank(i,j,cur);
134           cur^=1;
135       }
136     printf("%I64d
",ans);
137 }
138 
139 int main(){
140     while(scanf("%d%d",&n,&m),m+n){
141         init();
142         if(m==1){
143             int ans = 1;
144             For(i,n-1) if(!maze[i][1]) ans = 0;
145             if(maze[n][1]) ans = 0;
146             printf("%d
",ans);
147         }
148         else DP();
149     }
150     return 0;
151 }