NC17629. [NOI2010]旅行路线
描述
2010年，世博会在中国上海举办，吸引了数以千万计的中外游客前来参观。暑假期间小Z也来到了上海世博园，她对世博园的拥挤早有所闻，对有的展馆甚至要 排上好几个小时的队才能进入也做好了充分准备，但为了使得自己的世博之旅更加顺利舒畅，小Z决定在游玩之前先制定一份详细的旅行路线。
小Z搜集到了世博园的地图，她发现从整体上看世博园是一块非常狭长的区域，而每一个展馆占用了其中一个几乎相同大小的方块。因此可以将整个园区看成一个n × m的矩阵(n≤3)，其中每一个格子为一个主题展馆。
由于不同展馆受到的关注度会有一些差别，因此排队时间的长短也不尽相同。小Z根据统计信息给每一个展馆(x, y)标记了Tx,y = 0或1，如果Tx,y = 1，表示这个展馆非常热门，需要排很长时间的队；如果Tx,y = 0，表示这个展馆相对比较普通，几乎不需要排队即可进入参观。小Z希望能够制定一份合理的路线，使得能交替参观热门馆和普通馆，既不会因为总是参观热门馆 而长时间在排队，也不会因为总是参观普通馆而使得游览过于平淡。同时，小Z办事很讲究效率，她希望在游遍所有展馆的同时，又不会走冤枉路浪费体力。因此她 希望旅行路线满足以下几个限制：
她制定了一个长度为n*m的 01 序列L，她希望第i个参观的展馆(x,y)满足Tx,y=Li。
小Z想知道有多少条不同的旅行路线能够满足她的要求。由于最终的结果可能很大，小Z只想知道可行的旅行路线总数mod 11192869的值。
输入描述
第一行包含两个正整数n, m。
第2行至第n+ 1行，每行有m个01整数，其中第i+ 1行第j个数表示Ti,j。
第n+ 2行有n*m个01整数，其中第i个数表示Li的值。
输出描述
包含一个整数，表示可行的旅行路线总数mod 11192869的值。
示例1
输入:
2 2 1 0 0 1 1 0 1 0
输出:
4
说明:
这四条可行的旅行路线分别为：C++11(clang++ 3.9) 解法, 执行用时: 3905ms, 内存消耗: 476K, 提交时间: 2019-01-07 18:07:39
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
#define check(i, j) ((i) > 0 && (i) <= n && (j) > 0 && (j) <= m)
const int maxN = 60, MOD = 11192869;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
bool mp[5][maxN], L[maxN << 2], marked[5][maxN];
int n, m, ans;
inline bool Fail(int x, int y, int j)
{
switch (j)
{
case 0:
if (marked[x - 1][y + 2] && !marked[x - 1][y + 1]
&& (!marked[x][y + 2] || !marked[x + 1][y + 1]))
return 1;
if (marked[x + 1][y + 2] && !marked[x + 1][y + 1]
&& (!marked[x][y + 2] || !marked[x - 1][y + 1]))
return 1;
break;
case 1:
if (marked[x - 1][y - 2] && !marked[x - 1][y - 1]
&& (!marked[x][y - 2] || !marked[x + 1][y - 1]))
return 1;
if (marked[x + 1][y - 2] && !marked[x + 1][y - 1]
&& (!marked[x][y - 2] || !marked[x - 1][y + 1]))
return 1;
break;
case 2:
if (marked[x + 2][y - 1] && !marked[x + 1][y - 1]
&& (!marked[x + 2][y] || !marked[x + 1][y + 1]))
return 1;
if (marked[x + 2][y + 1] && !marked[x + 1][y + 1]
&& (!marked[x + 2][y] || !marked[x + 1][y - 1]))
return 1;
break;
case 3:
if (marked[x - 2][y - 1] && !marked[x - 1][y - 1]
&& (!marked[x - 2][y] || !marked[x - 1][y + 1]))
return 1;
if (marked[x - 2][y + 1] && !marked[x - 1][y + 1]
&& (!marked[x - 2][y] || !marked[x - 1][y - 1]))
return 1;
break;
}
return 0;
}
int Dfs(int i, int x, int y)
{
if (i > n * m - 1) return 1;
int tmp = 0; marked[x][y] = 1;
for (int j = 0; j < 4; ++j)
{
int u = x + dx[j], v = y + dy[j];
if (!Fail(x, y, j) && check(u, v) && !marked[u][v]
&& mp[u][v] == L[i + 1])
{
if (i == n * m - 1) ++tmp;
else tmp += Dfs(i + 1, u, v);
}
while (tmp >= MOD) tmp -= MOD;
}
marked[x][y] = 0;
return tmp;
}
inline int getint()
{
int res = 0; char tmp;
while (!isdigit(tmp = getchar()));
do res = (res << 3) + (res << 1) + tmp - '0';
while (isdigit(tmp = getchar()));
return res;
}
int main()
{
scanf("%d%d", &n, &m); int tot1 = 0, tot2 = 0;
for (int j = 0; j < m + 2; ++j)
marked[0][j] = marked[n + 1][j] = 1;
for (int i = 1; i < n + 1; ++i)
{
marked[i][0] = marked[i][m + 1] = 1;
//getchar();
for (int j = 1; j < m + 1; ++j)
tot1 += mp[i][j] = getint();
}
//getchar();
for (int i = 1; i < n * m + 1; ++i)
tot2 += L[i] = getint();
if (tot1 - tot2) {printf("0\n"); return 0;}
if (n == 1)
{
if (mp[1][m] == L[1]) ans += Dfs(1, 1, m);
if (m > 1 && mp[1][1] == L[1]) ans += Dfs(1, 1, 1);
printf("%d\n", ans);
return 0;
}
for (int j = 1; j < m + 1; ++j)
{
if (mp[n][j] == L[1]) ans += Dfs(1, n, j);
if (n > 1 && mp[1][j] == L[1]) ans += Dfs(1, 1, j);
while (ans >= MOD) ans -= MOD;
}
for (int i = 2; i < n; ++i)
{
if (mp[i][m] == L[1]) ans += Dfs(1, i, m);
if (m > 1 && mp[i][1] == L[1]) ans += Dfs(1, i, 1);
while (ans >= MOD) ans -= MOD;
}
printf("%d\n", ans % MOD);
return 0;
}