画圈圈 bzoj2170

圈圈 bzoj2170"/>

画圈圈 bzoj2170

注意此题是允许出现回路套回路的情况的，用射线法判断在图形内还是图形外，由于方格图的特殊性，只要记录在点上方的路径数的奇偶性就可以了，注意端点的时候只能取一个方向的端点。用括号表示法搞的

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>   
#include <map>
#include <string>  
#include <climits> 
#include <set>
#include <string>    
#include <sstream>
#include <utility>   
#include <ctime>using std::priority_queue;
using std::vector;
using std::swap;
using std::stack;
using std::sort;
using std::max;
using std::min;
using std::pair;
using std::map;
using std::string;
using std::cin;
using std::cout;
using std::set;
using std::queue;
using std::string;
using std::istringstream;
using std::make_pair;
using std::getline;
using std::greater;
using std::endl;
using std::multimap;
using std::deque;typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PAIR;
typedef multimap<int, int> MMAP;const int MAXN(200010);
const int MAXM(5010);
const int MAXE(10010);
const int HSIZE(13131);
const int SIGMA_SIZE(26);
const int MAXH(19);
const int INFI((INT_MAX-1) >> 1);
const int MOD(123456791);
const ULL BASE(31);
const LL LIM(10000000);
const int INV(-10000);int N, M;struct HASH_MAP
{int first[HSIZE];int next[MAXN], state[MAXN];int value[MAXN];int size;void init(){memset(first, -1, sizeof(first));size = 0;}void insert(int ts, int tv){int h = ts%HSIZE;for(int i = first[h]; ~i; i = next[i])if(state[i] == ts){value[i] += tv;if(value[i] >= MOD)value[i] -= MOD;return;}value[size] = tv;state[size] = ts;next[size] = first[h];first[h] = size++;}
} hm[2];HASH_MAP *cur, *last;
char mp[25][14];
int mul2[14];inline int getP(int ts, int i) {return (ts >> mul2[i])&1;}
inline void setP(int &ts, int i, int tv){ts = (ts&~(1 << mul2[i]))|(tv << mul2[i]);}inline int getQ(int ts, int i){return (ts >> mul2[i])&2;}
inline void setQ(int &ts, int i, int tv) { ts = (ts&~(2 << mul2[i]))|(tv << mul2[i]);}
inline void xorQ(int &ts, int i) {ts ^= (2 << mul2[i]);}void updata(int x, int y, int ts, int tv)
{int left = (y == 0)? 0: getP(ts, y);int up = (x == 0)? 0: getP(ts, y+1);int tts, Q = getQ(ts, y+1);if(mp[x][y] == '*'){if(left == 0 && up == 0 && Q){tts = ts;setQ(tts, y, 2);setQ(tts, y+1, 0);setP(tts, y, 0);setP(tts, y+1, 0);cur->insert(tts, tv);}return;}if(mp[x][y] == '#'){if(left == 0 && up == 0 && Q == 0){tts = ts;setQ(tts, y, 0);setQ(tts, y+1, 0);setP(tts, y, 0);setP(tts, y+1, 0);cur->insert(tts, tv);}return;}if(left == 0 && up == 0){if(x == N-1 || y == M-1) return;tts = ts;setQ(tts, y, Q);setQ(tts, y+1, 0);setP(tts, y, 1);setP(tts, y+1, 1);cur->insert(tts, tv);}elseif(left == 0 || up == 0){if(x < N-1){tts = ts;setQ(tts, y, Q);if(left != 0) xorQ(tts, y);setQ(tts, y+1, 0);setP(tts, y,  1);setP(tts, y+1, 0);cur->insert(tts, tv);}if(y < M-1){tts = ts;setQ(tts, y, Q);if(left != 0) xorQ(tts, y);setQ(tts, y+1, 0);setP(tts, y,  0);setP(tts, y+1, 1);cur->insert(tts, tv);}}else{tts = ts;setQ(tts, y, Q);xorQ(tts, y);setQ(tts, y+1, 0);setP(tts, y,  0);setP(tts, y+1, 0);cur->insert(tts, tv);}
}void solve()
{cur = hm;last = hm+1;last->init();last->insert(0, 1);for(int i = 0; i < N; ++i){int sz = last->size;for(int k = 0; k < sz; ++k)last->state[k] <<= 2;for(int j = 0; j < M; ++j){cur->init();sz = last->size;for(int k = 0; k < sz; ++k)updata(i, j, last->state[k], last->value[k]);swap(cur, last);}}int ans = 0;for(int i = 0; i < last->size; ++i)if(last->state[i] == 0){ans = last->value[i];break;}printf("%d\n", ans);
}int main()
{for(int i = 0; i <= 12; ++i)mul2[i] = i << 1;while(~scanf("%d%d", &N, &M)){for(int i = 0; i < N; ++i)scanf("%s", mp[i]);solve();}return 0;
}