题解 P1933 【[NOI2010]旅行路线】
在朴素搜索的基础上，加上一点剪枝即可过70分（当走过的区域将整个图分成了两个或两个以上的连通块时，直接舍去。
（深色部分为已走过或不能走的区域。）
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#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()
{
freopen("trip.in", "r", stdin);
freopen("trip.out", "w", stdout);
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;
scanf("\n");
for (int j = 1; j < m + 1; ++j)
tot1 += mp[i][j] = getint();
}
scanf("\n");
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;
}