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
114
Source
WA了好长时间。。不知道是orz谁的代码。。写完了发现和他写的一模一样。。我WA的原因是cur是全局的。。
Codes:
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 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("\n"); 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