剪枝爆搜
剪枝1:
如果位于以下形状的中心,直接判定无解,返回。
╋━╋━╋━╋
┃ ┃o┃ ┃
╋━╋━╋━╋
┃■┃x┃■┃
╋━╋━╋━╋
┃ ┃o┃ ┃
╋━╋━╋━╋
╋━╋━╋━╋
┃ ┃■┃ ┃
╋━╋━╋━╋
┃o┃x┃o┃
╋━╋━╋━╋
┃ ┃■┃ ┃
╋━╋━╋━╋
为什么是对的?有两种可能:
┏━┳━┳━┳━┳━┳━┓
┃┃┃ ┃ ┃ ┃ ┃ ┃
┣╋╋━╋━╋━╋━╋━┫
┃┗╋━╋━╋━╋■╋━┃■
┣━╋━╋━╋━╋━╋━┫
┃ ┃ ┃ ┃ ┃ ┃ ┃
┣━╋━╋━╋━╋━╋━┫
┃ ┃ ┃ ┃ ┃ ┃ ┃
┗━┻━┻━┻━┻━┻━┛
以边界为障碍,上的话就下不去了,下的话就上不去了。
┏━┳━┳━┳━┳━┳━┓
┃┃┃ ┃ ┃ ┃ ┃ ┃
┣╋╋━╋━╋━╋━╋━┫
┃┗╋■┃━╋■╋┓┃ ┃
┣━╋╋╋━╋━╋╋╋━┫
┃ ┃┃┃ ┃ ┃┃┃ ┃
┣━╋╋╋━╋━╋╋╋━┫
┃ ┃┗╋━╋━╋┛┃ ┃
┗━┻━┻━┻━┻━┻━┛
以跑了一圈,上的话就下不去了,下的话就上不去了。
剪枝2:
计算从当前点能到达的点,能到达的点的出路少于$1$的非终点个数有几个,如果大于$2$个,无解,如果有$1$个,只能走它。
因为有$1$个:
┏━┳━┳━┳━┳━┳━┳━┓
┃┃┃┏╋━╋━╋┓┃ ┃ ┃
┣╋╋╋╋━╋━╋╋╋━╋━┫
┃┗╋┛┃ ┃ ┃┗╋↑┃ ┃
┣━╋━╋━╋━╋━╋━╋━┫
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┣━╋━╋━╋━╋━╋━╋━┫
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
┗━┻━┻━┻━┻━┻━┻━┛
如果不走上面的格的话,后来在走的就只进不出了
如果大于$2$个,如果走任意一个格,其他的就只进不出了,
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
bool st[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
bool check(int x, int y) // 检查能到达的点的出路少于1的非终点个数有几个,如果大于2个,返回0,如果有比1少个,返回1
{
int cnt = 0;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (!st[a][b])
cnt ++ ;
}
return cnt <= 1;
}
int dfs(int x, int y, int u)
{
if (x == n && y == 1)
{
if (u == n * n) return 1;
return 0;
}
// 剪枝1
if (st[x - 1][y] && st[x + 1][y] && !st[x][y - 1] && !st[x][y + 1] ||
st[x][y - 1] && st[x][y + 1] && !st[x - 1][y] && !st[x + 1][y])
return 0;
int cnt = 0, sx, sy;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
// !(a == n && b == 1): 检查非终点, !st[a][b] :有没有走过,check(a, b) :剪枝2是不是无解
if (!(a == n && b == 1) && !st[a][b] && check(a, b))
{
cnt ++ ;
sx = a, sy = b;
}
}
int res = 0;
if (cnt > 1) return 0;
else if (cnt == 1)
{
// 剪枝2如果有1个情况
st[sx][sy] = true;
res += dfs(sx, sy, u + 1);
st[sx][sy] = false;
}
else
{
//继续搜
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (!st[a][b])
{
st[a][b] = true;
res += dfs(a, b, u + 1);
st[a][b] = false;
}
}
}
return res;
}
int main()
{
cin >> n;
// 边界
for (int i = 0; i <= n + 1; i ++ )
st[i][0] = st[i][n + 1] = st[0][i] = st[n + 1][i] = true;
st[1][1] = true;
cout << dfs(1, 1, 1) << endl;
return 0;
}