\nhttp:\/\/acm.buaa.edu.cn\/contest\/116\/problem\/F\/
\nhttp:\/\/acm.buaa.edu.cn\/problem\/746\/
\nhttp:\/\/www.xuebuyuan.com\/1798536.html<\/p>\n
\u5fc5\u987b\u7ecf\u8fc7 | \u53ef\u4ee5\u7ecf\u8fc7\u3002\u3002 \u53c2\u8003 FZU 1977. Pandora adventure
\n http:\/\/user.qzone.qq.com\/251815992\/blog\/1441374326<\/p>\n
\u683c\u5b50\u5b58\u50a8\u56db\u4e2a\u65b9\u5411\u7684\u901a\u884c\u4fe1\u606f\u3002\u3002\u53c2\u8003 ZOJ 2126. Rocket Mania
\nhttp:\/\/user.qzone.qq.com\/251815992\/blog\/1441548754 ;
\n\uff08\u4f46\u9700\u8981\u6ce8\u610f\u7684\u662f\uff01\u3002\u3002\u8fd9\u91cc\u662f\u56de\u8def\u3002\u3002\u6240\u4ee5\u4e0d\u5141\u8bb8\u63d2\u5934\u5728\u4efb\u610f\u4f4d\u7f6e\u4e2d\u65ad\uff01\uff09<\/p>\n
\r\n\r\nconst int N = 12, M = 1 << 20, _M = 3;\r\n\r\nint n, m;\r\nint b[N+1], bb[N+1];\r\n\r\nLL encode(){\r\n FLC(bb, -1); int n = 1; bb[0] = 0; LL s = 0;\r\n DWN(i, m+1, 0){\r\n if (!~bb[b[i]]) bb[b[i]] = n++;\r\n b[i] = bb[b[i]];\r\n s <<= _M; s |= b[i];\r\n }\r\n return s;\r\n}\r\n\r\nvoid decode(LL s){\r\n REP(i, m+1){\r\n b[i] = s & _U(_M);\r\n s >>= _M;\r\n }\r\n}\r\n\r\nconst int Prime = 9979;\r\n\r\nint d; struct hashTable{\r\n LL state[M]; int key[M]; int sz;\r\n int hd[Prime], nxt[M];\r\n\r\n void clear(){\r\n sz = 0;\r\n FLC(hd, -1);\r\n }\r\n\r\n void push(){\r\n LL s = encode();\r\n int x = s % Prime;\r\n\r\n for (int i=hd[x];~i;i=nxt[i]){\r\n if (state[i] == s){\r\n INC(key[i], d);\r\n return;\r\n }\r\n }\r\n state[sz] = s; key[sz] = d;\r\n nxt[sz] = hd[x]; hd[x] = sz;\r\n ++sz;\r\n assert(sz < M);\r\n }\r\n\r\n void roll(){\r\n REP(ii, sz) state[ii] <<= _M;\r\n }\r\n} H[2]; int src, des;\r\nint A[N+1][N+1], tx, ty;\r\n\r\n\r\nbool isBlock(int s){return s & 1;}\r\nbool isMust(int s){return s & 2;}\r\nbool isRight(int s){return s & 4;}\r\nbool isLeft(int s){return s & 8;}\r\nbool isDown(int s){return s & 16;}\r\nbool isUp(int s){return s & 32;}\r\n\r\nvoid init(){\r\n tx = -1, ty = -1; RD(n, m); REP_2(i, j, n, m) if (isMust(RD(A[i][j]))) tx = i, ty = j;\r\n REP(i, m) A[n][i] = 1; REP(i, n) A[i][m] = 1;\r\n}\r\n\r\nvoid solve(){\r\n src = 0, des = 1; H[des].clear(); RST(b); d = 1; H[des].push();\r\n\r\n int z = 0; REP(i, n){\r\n REP(j, m){\r\n\r\n if (isBlock(A[i][j])) continue;\r\n swap(src, des); H[des].clear();\r\n\r\n \/\/cout << i << " " << j << " "<< H[src].sz << endl;\r\n\r\n REP(ii, H[src].sz){\r\n decode(H[src].state[ii]); d = H[src].key[ii];\r\n\r\n int lt = b[j], up = b[j+1];\r\n bool dn = isDown(A[i][j]) && isUp(A[i+1][j]) && !isBlock(A[i+1][j]);\r\n bool rt = isRight(A[i][j]) && isLeft(A[i][j+1]) && !isBlock(A[i][j+1]);\r\n\r\n if (lt && up){\r\n if (lt == up){\r\n if (i*m+j>=tx*m+ty){\r\n int cnt = 0; REP(jj, m+1) if (b[jj]) ++cnt; \/\/ ?\r\n if (cnt == 2) INC(z, d);\r\n }\r\n }\r\n else{\r\n b[j] = b[j+1] = 0;\r\n REP(jj, m+1) if (b[jj] == lt) b[jj] = up;\r\n H[des].push();\r\n }\r\n }\r\n else if (lt || up){\r\n int t = lt | up;\r\n if (dn){\r\n b[j] = t; b[j+1] = 0;\r\n H[des].push();\r\n }\r\n if (rt){\r\n b[j] = 0; b[j+1] = t;\r\n H[des].push();\r\n }\r\n }\r\n else{\r\n\r\n if (!isMust(A[i][j])){\r\n H[des].push();\r\n }\r\n\r\n if (dn && rt){\r\n b[j] = b[j+1] = N-1;\r\n H[des].push();\r\n }\r\n }\r\n }\r\n }\r\n H[des].roll();\r\n }\r\n\r\n printf("%d\\n", z);\r\n}\r\n\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n Rush{\r\n init();\r\n solve();\r\n }\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[15],"tags":[45],"class_list":["post-1211","post","type-post","status-publish","format-standard","hentry","category-online","tag-dp"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-jx","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1211","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1211"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1211\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1211"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1211"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1211"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}