NC17708. Maze
描述
输入描述
The first line contains two integer n, m.
In following n lines, each line contains m-1 integers, which are the array v.
In following n-1 lines, each line contains m integers, which are the array h.
1 <= n <= 7
1 <= m <= 7
0 <= v[i][j] <= 1
0 <= h[i][j] <= 1
输出描述
You should output the anwer in one line.
示例1
输入:
2 2 0 0 0 0
输出:
164
说明:
If there is 0 or 1 wall, the beauty is 4 * 4 = 16示例2
输入:
2 2 0 1 0 1
输出:
26
说明:
The two existing wall forms shape L.C++14(g++5.4) 解法, 执行用时: 218ms, 内存消耗: 87784K, 提交时间: 2018-09-11 19:45:59
#include <iostream>
#include <ios>
#include <cstdint>
#include <vector>
using ul = std::uint32_t;
using ull = std::uint64_t;
using li = std::int32_t;
using ll = std::int64_t;
using vul = std::vector<ul>;
using vvul = std::vector<vul>;
using vvvul = std::vector<vvul>;
const ul base = 1e9 + 7;
const li basel = base;
ul plus(ul a, ul b)
{
return a + b < base ? a + b : a + b - base;
}
ul minus(ul a, ul b)
{
return a < b ? a + base - b : a - b;
}
ul times(ul a, ul b)
{
return ull(a) * b % base;
}
void exgcd(li a, li b, li& x, li& y)
{
if (b) {
exgcd(b, a % b, y, x);
y -= x * (a / b);
} else {
x = 1;
y = 0;
}
}
ul inverse(ul a)
{
li x, y;
exgcd(base, a, x, y);
return y < 0 ? y + basel : y;
}
vvvul prevans(1 << 16, vvul(9, vul(9, 0)));
vvvul currans(1 << 16, vvul(9, vul(9, 0)));
vul legalcuts;
vvul h(8, vul(8, 1));
vvul v(8, vul(8, 1));
ul n, m;
vul parts;
vul belongpart(9, 0);
vul nexbelongpart(9, 0);
std::ostream& print(std::ostream& os, ul cut) {
for (ul i = 0; i <= m; ++i) {
if (i) {
std::cout << "口";
}
if (cut >> i >> i & 1) {
std::cout << ')';
}
if (cut >> i >> i & 2) {
std::cout << '(';
}
}
return os;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin >> n >> m;
for (ul i = 1; i <= n; ++i) {
for (ul j = 1; j != m; ++j) {
std::cin >> v[i][j];
}
}
for (ul i = 1; i != n; ++i) {
for (ul j = 1; j <= m; ++j) {
std::cin >> h[i][j];
}
}
for (ul cut = 0; cut != (1 << m << m << 2); ++cut) {
if ((cut & 3) != 2 || (cut >> m >> m & 3) != 1) {
continue;
}
bool flag = true;
parts.resize(0);
for (ul k = 0; k <= m; ++k) {
ul temp2 = cut >> k >> k & 3;
if (temp2 & 1) {
if (parts.empty()) {
flag = false;
break;
}
parts.pop_back();
}
if (temp2 & 2) {
parts.push_back(k + 1);
}
if (parts.empty() && k != m) {
flag = false;
break;
}
belongpart[k + 1] = parts.back();
}
if (parts.size()) {
flag = false;
}
if (!flag) {
continue;
}
legalcuts.push_back(cut);
}
prevans[(1 << m << m << 1) - 2][0][0] = 1;
for (ul i = 1; i <= n; ++i) {
for (ul j = 1; j <= m; ++j) {
for (ul cut : legalcuts) {
for (ul a = 0; a <= m + 1; ++a) {
for (ul b = 0; b <= m + 1; ++b) {
currans[cut][a][b] = 0;
}
}
}
for (ul cut : legalcuts) {
parts.resize(0);
for (ul k = 0; k <= m; ++k) {
ul temp2 = cut >> k >> k & 3;
if (temp2 & 1) {
parts.pop_back();
}
if (temp2 & 2) {
parts.push_back(k + 1);
}
belongpart[k + 1] = parts.back();
}
ul jto;
if (belongpart[j] == j) {
for (jto = j + 1; jto <= m && belongpart[jto] != j; ++jto) {
}
}
for (bool up : {false, true}) {
if (up < h[i - 1][j]) {
continue;
}
for (bool left : {false, true}) {
if (left < v[i][j - 1]) {
continue;
}
ul nexcut = cut;
if (up) {
ul temp = j - 1;
nexcut |= 2 << temp << temp | 1 << temp << temp << 2;
if ((~cut >> temp >> temp & 2) && (cut >> temp >> temp >> 2 & 1)) {
ul temp2 = 1;
ul k;
for (k = temp; ; --k) {
if (nexcut >> k >> k & 2) {
--temp2;
}
if (~nexcut >> k >> k & 1) {
if (!temp2) {
break;
}
}
if (nexcut >> k >> k & 1) {
++temp2;
}
}
nexcut |= 1 << k << k;
} else if ((cut >> temp >> temp & 2) && (~cut >> temp >> temp >> 2 & 1)) {
ul temp2 = 1;
ul k;
for (k = temp + 1; ; ++k) {
if (nexcut >> k >> k & 1) {
--temp2;
}
if (~nexcut >> k >> k & 2) {
if (!temp2) {
break;
}
}
if (nexcut >> k >> k & 2) {
++temp2;
}
}
nexcut |= 2 << k << k;
}
}
ul nexnexcut = nexcut;
if (!left) {
ul temp = j - 1;
nexnexcut &= ~(3 << temp << temp);
if ((~nexcut >> temp >> temp & 2) && (nexcut >> temp >> temp & 1)) {
ul temp2 = 0;
ul k;
for (k = temp - 1; ; --k) {
if (nexnexcut >> k >> k & 2) {
if (!temp2) {
break;
}
--temp2;
}
if (nexnexcut >> k >> k & 1) {
++temp2;
}
}
nexnexcut &= ~(2 << k << k);
} else if ((nexcut >> temp >> temp & 2) && (~nexcut >> temp >> temp & 1)) {
ul temp2 = 0;
ul k;
for (k = temp + 1; ; ++k) {
if (nexnexcut >> k >> k & 1) {
if (!temp2) {
break;
}
--temp2;
}
if (nexnexcut >> k >> k & 2) {
++temp2;
}
}
nexnexcut &= ~(1 << k << k);
}
}
ul nex = nexnexcut;
//print(print(std::cout << i << ' ' << j << ' ', cut) << ' ' << up << ' ' << left << ' ', nex) << std::endl;
parts.resize(0);
for (ul k = 0; k <= m; ++k) {
ul temp2 = nex >> k >> k & 3;
if (temp2 & 1) {
parts.pop_back();
}
if (temp2 & 2) {
parts.push_back(k + 1);
}
nexbelongpart[k + 1] = parts.back();
}
for (ul a = 0; a <= m + 1; ++a) {
if (a != 0 && a != m + 1 && belongpart[a] != a) {
continue;
}
for (ul b = 0; b <= m + 1; ++b) {
if (b != 0 && b != m + 1 && belongpart[b] != b) {
continue;
}
if ((a == m + 1) != (b == m + 1)) {
continue;
}
if (a == m + 1 && b == m + 1) {
currans[nex][a][b] = plus(currans[nex][a][b], prevans[cut][a][b]);
} else if (!a && !b) {
currans[nex][nexbelongpart[j]][nexbelongpart[j]] = plus(currans[nex][nexbelongpart[j]][nexbelongpart[j]], prevans[cut][a][b]);
currans[nex][0][nexbelongpart[j]] = plus(currans[nex][0][nexbelongpart[j]], prevans[cut][a][b]);
currans[nex][nexbelongpart[j]][0] = plus(currans[nex][nexbelongpart[j]][0], prevans[cut][a][b]);
currans[nex][0][0] = plus(currans[nex][0][0], prevans[cut][a][b]);
} else if (a && !b) {
if (a != j) {
currans[nex][nexbelongpart[a]][nexbelongpart[j]] = plus(currans[nex][nexbelongpart[a]][nexbelongpart[j]], prevans[cut][a][b]);
currans[nex][nexbelongpart[a]][0] = plus(currans[nex][nexbelongpart[a]][0], prevans[cut][a][b]);
} else {
if (up) {
if (jto > m) {
continue;
}
currans[nex][jto][nexbelongpart[j]] = plus(currans[nex][jto][nexbelongpart[j]], prevans[cut][a][b]);
currans[nex][jto][0] = plus(currans[nex][jto][0], prevans[cut][a][b]);
} else {
currans[nex][nexbelongpart[j]][nexbelongpart[j]] = plus(currans[nex][nexbelongpart[j]][nexbelongpart[j]], prevans[cut][a][b]);
currans[nex][nexbelongpart[j]][0] = plus(currans[nex][nexbelongpart[j]][0], prevans[cut][a][b]);
}
}
} else if (!a && b) {
if (b != j) {
currans[nex][nexbelongpart[j]][nexbelongpart[b]] = plus(currans[nex][nexbelongpart[j]][nexbelongpart[b]], prevans[cut][a][b]);
currans[nex][0][nexbelongpart[b]] = plus(currans[nex][0][nexbelongpart[b]], prevans[cut][a][b]);
} else {
if (up) {
if (jto > m) {
continue;
}
currans[nex][nexbelongpart[j]][jto] = plus(currans[nex][nexbelongpart[j]][jto], prevans[cut][a][b]);
currans[nex][0][jto] = plus(currans[nex][0][jto], prevans[cut][a][b]);
} else {
currans[nex][nexbelongpart[j]][nexbelongpart[j]] = plus(currans[nex][nexbelongpart[j]][nexbelongpart[j]], prevans[cut][a][b]);
currans[nex][0][nexbelongpart[j]] = plus(currans[nex][0][nexbelongpart[j]], prevans[cut][a][b]);
}
}
} else {
if (a != j && b != j) {
currans[nex][nexbelongpart[a]][nexbelongpart[b]] = plus(currans[nex][nexbelongpart[a]][nexbelongpart[b]], prevans[cut][a][b]);
} else if (a != j && b == j) {
if (up) {
if (jto > m) {
continue;
}
currans[nex][nexbelongpart[a]][jto] = plus(currans[nex][nexbelongpart[a]][jto], prevans[cut][a][b]);
} else {
currans[nex][nexbelongpart[a]][nexbelongpart[b]] = plus(currans[nex][nexbelongpart[a]][nexbelongpart[b]], prevans[cut][a][b]);
}
} else if (a == j && b != j) {
if (up) {
if (jto > m) {
continue;
}
currans[nex][jto][nexbelongpart[b]] = plus(currans[nex][jto][nexbelongpart[b]], prevans[cut][a][b]);
} else {
currans[nex][nexbelongpart[a]][nexbelongpart[b]] = plus(currans[nex][nexbelongpart[a]][nexbelongpart[b]], prevans[cut][a][b]);
}
} else {
if (up) {
currans[nex][jto][jto] = plus(currans[nex][jto][jto], prevans[cut][a][b]);
} else {
currans[nex][nexbelongpart[a]][nexbelongpart[b]] = plus(currans[nex][nexbelongpart[a]][nexbelongpart[b]], prevans[cut][a][b]);
}
}
}
}
}
}
}
}
std::swap(prevans, currans);
}
}
ul finalans = 0;
for (ul cut : legalcuts) {
for (ul a = 1; a <= m + 1; ++a) {
finalans = plus(finalans, prevans[cut][a][a]);
}
}
std::cout << finalans << std::endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 12ms, 内存消耗: 1508K, 提交时间: 2018-09-04 13:05:41
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXNUM 111111
using ll = long long;
ll mod = 1e9 + 7;
void add(ll &a, ll b)
{
a += b;
if (a >= mod)
a -= mod;
}
const int hashsize = 111111;
typedef struct hashmap {
int next[MAXNUM], pos[MAXNUM], first[hashsize], edgenum;
long long totalnum, item[MAXNUM], itemkey[MAXNUM];
void hadd(long long key, long long num)
{
int x = key % hashsize;
for (int i = first[x]; i; i = next[i])
if (itemkey[pos[i]] == key)
{
add(item[pos[i]], num);
return;
}
next[edgenum] = first[x], pos[edgenum] = totalnum;
first[x] = edgenum++;
item[totalnum] = num, itemkey[totalnum] = key,
totalnum++;
}
void init()
{
edgenum = 1, totalnum = 0;
memset(first, 0, sizeof(first));
}
}hashmap;
hashmap h[2];
int bit[22];
#define rep(i,start,end) for(int i=start;i<end;i++)
void getbit()
{
for (int i = 0; i < 15; i++)
bit[i] = 3 * i;
}
int n, m;
void decode(long long con, ll num[])
{
rep(i, 0, m + 5)
{
num[i] = con & 7;
con >>= 3;
}
}
long long encode(ll num[])
{
int count = 1;
ll code[22];
memset(code, -1, sizeof(code));
code[0] = 0;
long long st = 0;
rep(i, 0, m)
{
if (code[num[i]] == -1)
code[num[i]] = count++;
long long x = code[num[i]];
st |= (x << bit[i]);
}
rep(i, m, m + 2)
if (code[num[i]] != -1)
st |= (code[num[i]] << bit[i]);
if (code[num[m]] > 0 && code[num[m + 1]] > 0 && num[m] == num[m + 1])
num[m + 4] = 1;
rep(i, m + 2, m + 5)
st |= (num[i] << bit[i]);
return st;
}
void connect(ll num2[], int s1, int s2)
{
int k = min(s1, s2);
rep(i, 0, m + 2)
if (num2[i] == s1 || num2[i] == s2)
num2[i] = k;
}
int sleft[22][22], sup[22][22];
long long res,num2[22];
void dp()
{
bool type = 1;
h[0].init();
ll middlenum[22];
h[0].hadd(0, 1);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
h[type].init();
for (int k = 0; k < h[!type].totalnum; k++)
{
long long state = h[!type].itemkey[k],
num = h[!type].item[k];
decode(state, middlenum);
int y1 = 2, y2 = 2;
if (sleft[i][j] == 1)
y1 = 1;
if (sup[i][j] == 1)
y2 = 1;
rep(k1,0,y1)
rep(k2, 0, y2)
{
if (!i&&k2)
continue;
if (!j&&k1)
continue;
rep(i2,0,2)
rep(j2, 0, 2)
{
if (!i2&&middlenum[m + 2])
continue;
if (!j2&&middlenum[m + 3])
continue;
memcpy(num2, middlenum, (m + 5) * sizeof(ll));
num2[j] = 15;
if (k1)
connect(num2, num2[j], middlenum[j - 1]);
if (k2)
connect(num2, num2[j], middlenum[j]);
num2[m + 2] = i2, num2[m + 3] = j2;
if (i2&&!middlenum[m+2])
num2[m] = num2[j];
if (j2&&!middlenum[m+3])
num2[m + 1] = num2[j];
h[type].hadd(encode(num2), num);
}
}
}
type = !type;
}
res = 0;
rep(i, 0, h[!type].totalnum)
{
long long state = h[!type].itemkey[i],
num = h[!type].item[i];
decode(state, middlenum);
if (middlenum[m + 4])
add(res, num);
}
}
int main(void)
{
getbit();
scanf("%d%d", &n, &m);
rep(i, 0, n)
rep(j, 1, m)
scanf("%d", &sleft[i][j]);
rep(i, 1, n)
rep(j, 0, m)
scanf("%d", &sup[i][j]);
dp();
printf("%lld\n", res);
}