一、深搜尝试
上来简单一看,无脑暴搜开始!
注意
//马所在的位置
ctrl[x][y] = 1;
ctrl[x - 1][y - 2] = 1;
ctrl[x - 2][y - 1] = 1;
ctrl[x + 1][y + 2] = 1;
ctrl[x + 2][y + 1] = 1;
ctrl[x - 2][y + 1] = 1;
ctrl[x - 1][y + 2] = 1;
ctrl[x + 1][y - 2] = 1;
ctrl[x + 2][y - 1] = 1;
这里面有一个细节,有的网友在计算马的控制范围时,简单粗暴的使用了上面的代码,这是不对的,因为没有判断\(x+2\)会不会越界,\(x-2\)会不会越界等,会有问题的。
正确的初始化马的位置代码如下:
//增量数组,delta
int d[8][2] = {
{1, 2},
{1, -2},
{-1, 2},
{-1, -2},
{2, 1},
{2, -1},
{-2, 1},
{-2, -1}};
//马的实际控制范围
for (int i = 0; i < 8; i++) {
int tx = mx + d[i][0], ty = my + d[i][1];
if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) ctrl[tx][ty] = 1;
}
//马所在的位置你也不能走,也踢你~
ctrl[mx][my] = 1;
完整的dfs代码如下:
#include <bits/stdc++.h>
using namespace std;
int ctrl[21][21];
int cnt, n, m;
int mx, my;
//深搜
void dfs(int x, int y) {
if (x > n || y > m) return;
if (x == n && y == m) {
cnt++;
return;
}
if (ctrl[x][y] == 1 || x > n || y > m) return;
if (!ctrl[x + 1][y]) dfs(x + 1, y);//向右
if (!ctrl[x][y + 1]) dfs(x, y + 1);//向下
}
//增量数组,delta
int d[8][2] = {
{1, 2},
{1, -2},
{-1, 2},
{-1, -2},
{2, 1},
{2, -1},
{-2, 1},
{-2, -1}};
int main() {
//读入B点坐标和马的坐标
cin >> n >> m >> mx >> my;
//马的实际控制范围
for (int i = 0; i < 8; i++) {
int tx = mx + d[i][0], ty = my + d[i][1];
if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) ctrl[tx][ty] = 1;
}
//马所在的位置你也不能走,也踢你~
ctrl[mx][my] = 1;
//深搜
dfs(0, 0);
//输出
printf("%d\n", cnt);
}
这么写完一提交,TLE了两个测试点。浪费一下下载机会,看一下,发现是极限数据,棋盘大小:\(n=20,m=20\),超时了。
2、为什么深搜会超时
都知道这道题数据量\(n,m<=15\)时可以使用深搜和递推,\(n,m>15\)时需要使用递推,那为什么深搜搞不定呢?理由:
上面是我想的原因,大神勿喷啊!重复计算才是万恶之首啊!!那解决方案也就到来了~
3、递推(动态规划)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 22;
LL f[N][N]; //递推小心爆INT,不开LL见祖宗
int ctrl[N][N]; //定义马的控制范围,一般采用int数组进行状态标识,不采用bool,因为1,0比true和false写的快
int n, m, x, y; //B点(目标点)的坐标,马的坐标
//增量数组,delta
int d[8][2] = {
{1, 2},
{1, -2},
{-1, 2},
{-1, -2},
{2, 1},
{2, -1},
{-2, 1},
{-2, -1}};
int main() {
//读入B点坐标和马的坐标
cin >> n >> m >> x >> y;
//马的实际控制范围
for (int i = 0; i < 8; i++) {
int tx = x + d[i][0], ty = y + d[i][1];
if (tx >= 0 && tx <= n && ty >= 0 && ty <= m) ctrl[tx][ty] = 1;
}
//马所在的位置你也不能走,也踢你~
ctrl[x][y] = 1;
//如果原点在马的控制范围内,那么就是无法出发
//如果原点不在马的控制范围内,那么就是有一种方法
if (ctrl[0][0]) f[0][0] = 0;
else f[0][0] = 1;
//开始递推
for (int i = 0; i <= n; i++) //遍历整个棋盘
for (int j = 0; j <= m; j++) {
//在马的控制范围内,就放弃掉这个点,路线条数为0,默认就是0,不需要改变,直接 continue即可。
if (ctrl[i][j])continue;
//不是第0行,可以从上一行递推过来
if (i > 0) f[i][j] += f[i - 1][j];
//不是第0列,可以从上一列递推过来
if (j > 0) f[i][j] += f[i][j - 1];
}
//输出结果
cout << f[n][m];
}