【wikioi】1010 过河卒

题目链接

算法:DFS+剪枝

14.01.02 PS: 递推应该也可以的,改天看看

刚开始最容易想到的是朴素搜索

#include <iostream>
using namespace std;
int n, m, X, Y;
int ans = 0;
void dfs(int i, int j)
{
if(i == 0 && j == 0){ans++; return;}
if(i<0||j<0||(i==X&&j==Y) ||
(i==X-2&&(j==Y-2||j==Y-1||j==Y+1)) ||
(i==X+1&&(j==Y-2||j==Y+1||j==Y+2)) ||
(i==X-1&&(j==Y-2||j==Y+2)) ||
(i==X+2&&(j==Y-1||j==Y+1)) )
return;
dfs(i,j-1); dfs(i-1,j);
}
int main()
{
cin >> n >> m >> X >> Y;
dfs(n, m);
cout << ans << endl;
return 0;
}

虽然能AC,但是数据一大就TLE了。

然后想到的是剪枝

//简单的搜索
#include <iostream>
using namespace std;
const int N = 15, M = 15;
int n, m, X, Y;
int f[N+2][M+2] = {0};
void dfs(int i, int j)
{
//一系列复杂的判断= =
if((i==X&&j==Y) ||
(i==X-2&&(j==Y-2||j==Y-1||j==Y+1)) ||
(i==X+1&&(j==Y-2||j==Y+1||j==Y+2)) ||
(i==X-1&&(j==Y-2||j==Y+2)) ||
(i==X+2&&(j==Y-1||j==Y+1)) )
return;
if(j-1>0 && !f[i][j-1]) dfs(i,j-1);
if(i-1>0 && !f[i-1][j]) dfs(i-1,j);
f[i][j] = f[i][j-1] + f[i-1][j]; //路径数等于上面的加上左边的(这是逆向的dfs)
}
int main()
{
f[1][1] = 1;
cin >> n >> m >> X >> Y;
X++; //将下标归为以1开始
Y++; //将下标归为以1开始
dfs(n+1, m+1);
cout << f[n+1][m+1] << endl;
return 0;
}

AC

上一篇:BP神经网络公式推导及实现(MNIST)


下一篇:Linux同步时间命令ntpdate