codevs1010——过河卒（DP||DFS）

题目链接

如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。

　　棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定: C不等于A，同时C不等于B）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。

$1<=n,m<=15$

输入描述

一行四个数据，分别表示B点坐标和马的坐标。

输出描述

一个数据，表示所有的路径条数。

样例输入

6 6 3 2

样例输出

思路

递推写法：

首先将在马的控制范围内的九个点标记出来，在递推的时候隔开这九个点即可。

状态转移方程：$dp[i][j]=dp[i-1][j]+dp[i][j-1]$

DFS：

同样需要标记九个点，然后就是可以转换成DFS+回溯的问题了

AC代码

DP

总时间耗费: 10ms
总内存耗费: 364 kB

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
#include <time.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define pi acos(-1.0)
#define INF 0x7f7f7f7f
#define lson o<<1
#define rson o<<1|1
#define bug cout<<"-------------"<<endl
#define debug(...) cerr<<"["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"<<"\n"
const double E=exp(1);
const int maxn=1e2+10;
const int mod=1e9+7;
using namespace std;
int dp[maxn][maxn];
int dir[8][2]={1,2,1,-2,2,1,2,-1,-1,2,-1,-2,-2,-1,-2,1};
int main(int argc, char const *argv[])
{
	ios::sync_with_stdio(false);
	int n,m;
	int x,y;
	ms(dp,0);
	cin>>n>>m;
	cin>>x>>y;
	dp[x][y]=-1;
	for(int i=0;i<8;i++)
		dp[x+dir[i][0]][y+dir[i][1]]=-1;
	if(dp[0][0]==-1)
	{
		cout<<0<<endl;
		return 0;
	}
	dp[0][0]=1;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			if(dp[i][j]!=-1)
			{
				if(i&&dp[i-1][j]!=-1)
					dp[i][j]+=dp[i-1][j];
				if(j&&dp[i][j-1]!=-1)
					dp[i][j]+=dp[i][j-1];
			}
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}

DFS

总时间耗费: 934ms
总内存耗费: 7 MB

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
#include <time.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define pi acos(-1.0)
#define INF 0x7f7f7f7f
#define lson o<<1
#define rson o<<1|1
#define bug cout<<"-------------"<<endl
#define debug(...) cerr<<"["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"<<"\n"
const double E=exp(1);
const int maxn=1e3+10;
const int mod=1e9+7;
using namespace std;
int dir[8][2]={1,2,1,-2,2,1,2,-1,-1,2,-1,-2,-2,1,-2,-1};
int dir1[2][2]={1,0,0,1};
int n,m;
int ans;
int _map[maxn][maxn];
int vis[maxn][maxn];
void dfs(int x,int y)
{
	if(vis[x][y]==-1||x<0||x>n||y<0||y>m)
		return ;
	if(x==n&&y==m)
	{
		ans++;
		return ;
	}
	vis[x][y]=1;
	for(int i=0;i<2;i++)
	{
		int dx=x+dir1[i][0];
		int dy=y+dir1[i][1];
		if(!vis[dx][dy]&&dx>=0&&dx<=n&&dy>=0&&dy<=m&&_map[dx][dy]!=-1)
		{
			dfs(dx,dy);
			vis[dx][dy]=0;
		}
	}
}
int main(int argc, char const *argv[])
{
	ios::sync_with_stdio(false);
	int x,y;
	cin>>n>>m>>x>>y;
	ms(_map,0);
	ms(vis,0);
	_map[x][y]=-1;
	for(int i=0;i<8;i++)
		_map[x+dir[i][0]][y+dir[i][1]]=-1;
	dfs(0,0);
	cout<<ans<<endl;
	return 0;
}