| input | output |
|---|---|
4 4 **.. .... .... .... |
2 |
4 4 .... .... .... .... |
6 |
插头dp的一条入门。
http://wenku.baidu.com/view/4fe4ac659b6648d7c1c74633.html
http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710343.html
#include <bits/stdc++.h> using namespace std ; const int N = 15 ; const int M = 30007 ; const int MAXN = 1000010; int n , m ; int maze[N][N] ; int code[N] ; int ch[N] ; int ex , ey ; struct HASHMAP { int head[M] , next[MAXN] , tot ; long long st[MAXN] , f[MAXN] ; void init() { memset( head , -1 , sizeof head ) ; tot = 0 ; } void push( long long state , long long ans ) { int u = state % M ; for( int i = head[u] ; ~i ; i = next[i] ) { if( st[i] == state ) { f[i] += ans ; return ; } } st[tot] = state ; f[tot] = ans ; next[tot] = head[u] ; head[u] = tot++ ; } } mp[2] ; void decode ( int* code , int m , long long st ) { for( int i = m ; i >= 0 ; --i ) { code[i] = st&7 ; st >>= 3 ; } } long long encode( int *code , int m ) { int cnt = 1 ; long long st = 0 ; memset( ch , -1 , sizeof ch) ; ch[0] = 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 left , up ; for( int k = 0 ; k < mp[cur].tot ; ++k ) { decode( code , m , mp[cur].st[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); mp[cur^1].push( encode(code,m) , mp[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 ); mp[cur^1].push(encode(code,m),mp[cur].f[k]) ; } } else if( ( left && ( !up ) ) || ( up && (!left ) ) ) { int t ; if( left ) t = left ; else t = up ; if( maze[i][j+1] ) { code[j-1] = 0 ; code[j] = t ; mp[cur^1].push( encode(code,m) , mp[cur].f[k] ) ; } if( maze[i+1][j] ) { code[j-1] = t ; code[j] = 0 ; if( j == m ) shift( code , m ); mp[cur^1].push(encode(code,m),mp[cur].f[k]); } } else { if( maze[i][j+1] && maze[i+1][j] ) { code[j-1] = code[j] = 13 ; mp[cur^1].push( encode(code,m),mp[cur].f[k]); } } } } void dpblock( int i , int j , int cur ) { for( int k = 0 ; k < mp[cur].tot ; ++k ) { decode( code , m , mp[cur].st[k] ); code[j-1] = code[j] = 0 ; if( j == m ) shift( code , m ); mp[cur^1].push( encode(code,m) , mp[cur].f[k] ); } } void Solve() { int v = 0 ; mp[v].init(); mp[v].push(0,1); for( int i = 1 ; i <= n ; ++i ) { for( int j = 1 ; j <= m ; ++j ) { mp[v^1].init() ; if( maze[i][j] ) dpblank( i , j , v ) ; else dpblock( i , j , v ); v ^= 1 ; } } long long ans = 0 ; for( int i = 0 ; i < mp[v].tot ; ++i ) ans += mp[v].f[i]; printf("%lld\n",ans); } char s[20]; int main () { while( ~scanf("%d%d",&n,&m) ) { ex = 0 ; memset( maze , 0 , sizeof maze ) ; for( int i = 1 ; i <= n ; ++i ) { scanf("%s",s); for( int j = 0 ; j < m ; ++j ) { if( s[j] == ‘.‘ ) { ex = i , ey = j + 1 ; maze[i][j+1] = 1 ; } } } if( !ex ) { puts("0"); continue ; } else Solve(); } return 0 ; }
原文：http://www.cnblogs.com/hlmark/p/4371248.html
