#include
#include
#include
#include
#include
#include
#include
#include "assert.h" #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PB push_back #define MP make_pair #define FR(i,n) for( long long i = 0; i < n; i ++ ) #define FOR(i,a,n) for(long long i = a; i < n; i ++) #define FREACH(it,v) for( typeof(v.end()) it = v.begin(); it != v.end(); it ++ ) #define EPS 1e-9 using namespace std; typedef long long ll; // For the instance in the website, this solution runs in 0.128 in my laptop (13-inch Macbook). /* N is the largest dimension in the input (which we assume, by rotating the input,corresponds to the number of columns). It is possible not to hard-code this, at a possible cost for efficiency coming from using C++ vectors or dynamic allocation, instead of arrays */ const int N_MAX=100; // M is the smallest dimension in the input. const int M_MAX=9; // map of the datacenter char dc[N_MAX][M_MAX]; int N,M; /* We consider the graph in which every cell of the grid is a node, and a horizontal/vertical border betwen two cells induces an edge. We count the number of subgraphs of the grid such that each node that we do not own has degree 0, each node that we own other than the endpoints has degree 2, and the endpoints have degree 1. Using results from introductory graph theory, such subgraphs are exactly the paths we are looking for */ /* Dynamic programming solution. We try all possible ways of doing the path for the top row, then see how many ways of completing them there are, then keep doing this recursively. At each point, all the information we care about is what did the path do in the previous row. The state for a row is encoded by an array. The i^th number of the array contains: - In its last bit, whether the path has to go north (to match the previous row) - In the second last bit, if the path goes north, whether it comes down - In the rest of the bits, where does the path come down - Bits that are not necessary to represent the current state (e.g. the second last bit when the last one is set to 0) are set to 0. */ /* Note that I am assuming that the answer does not overflow. If it does, then we can use a biginteger library. This can be done either by storing bigintegers in our dp table, or if we know a good upper bound on our result, storing the result modulo several different primes in the dp table, and using the chinese remainder theorem to reconstruct the answer in the end. The memory cost for both solutions should be around the same, but the solution using chinese remainder theorem is probably more efficient, I believe (for division/multiplication, the cost for operating on k integers will probably be better than the one of operating of a biginteger k times the size of an integer). */ /* The number of states for a row when there are N_MAX columns. Obtained using the recurrence formula n[i] = 2*n[i-1] + sum of j from 1 to i-1 of n[j-1]*n[n-j-1]*/ const int M_MAX_STATES = 218318; int nstates; int states[M_MAX_STATES][M_MAX]; ll dp[N_MAX][M_MAX_STATES]; // we build all possible states for a row, and assign them to identifiers void build(); // lookup table to find the identifier for a state map< vector
, int > lookup; int elems[M_MAX]; // recursive brute force to build all states void recurse(int col) { while(col
(elems,elems+M)] = nstates; nstates++; } else { elems[col]=0; recurse(col+1); elems[col]=1; recurse(col+1); elems[col]=-1; FOR(j,col+1,M) { if(elems[j]!=-1) break; elems[col]=3|(j<<2); elems[j]=3|(col<<2); recurse(col+1); elems[j]=-1; elems[col]=-1; } } } void build() { memset(elems,-1,sizeof(elems)); lookup.clear(); nstates=0; recurse(0); } // we do memoization. That way we avoid computing the whole DP table. ll memoize(int row,int id) { ll& answer=dp[row][id]; if(answer!=-1) { return answer; } answer=0; // current state int curstate[M]; // state to which we transition in the dp table vector
nextstate(M); int nextid; FR(i,M) curstate[i]=states[id][i]; bool up[M]; FR(i,M) up[i]=(curstate[i]&1); // for all possible places to go down FR(down,(1<
0) break; // we initialize the next state FR(i,M) { nextstate[i]=((down&(1<
0); } // keep track of beginning/end of segments along the row int other[M]; memset(other,-1,sizeof(other)); // while we are not in the end int cnt=0,bg,nd; for(;;) { // skip all positions that we do not own while(cnt < M && dc[row][cnt]=='1' && !up[cnt] &&!(down&(1<
2 if(up[cnt]&&(down&(1<
>2)==cur) goto FOO; if(!(states[id][cur]&2)) break; cur=states[id][cur]>>2; if(other[cur]==cur||other[cur]==-1) break; cur=other[cur]; } } break; } } } cnt++; } bool marked[M]; memset(marked,0,sizeof(marked)); // update the connection between the different parts of the path, as // seen by the next row FR(i,M) { if(!marked[i]&&other[i]!=-1&&(down&(1<
>2; assert(other[j]!=-1); j=other[j]; if(down&(1<
=W) { FR(i,H) FR(j,W) cin >> dc[i][j]; } else { FR(i,H) FR(j,W) cin >> dc[j][i]; } N=max(W,H); M=min(W,H); // we do not make any difference between endpoints, and this simplifies the code later FR(i,N) FR(j,M) if(dc[i][j]=='3') dc[i][j]='2'; build(); cout << memoize(0,0) << endl; }