简简单单地AC

今天下午第二题,难度不难,因为数据小,用dfs很简单 *接下来,代码奉上。

//其实直接把马可以攻击到的地方建个索引就好了,像我这样每次判断其实很浪费时间
//哦对了,要注意,我m,n和题目的m,n是相反的,不过无所谓
#include<iostream>
using namespace std;
int m,n,ans=0,hx,hy;
int choose(int a,int b)
{
if(a==hx && b==hy) return 0;
if(a+2==hx && b+1==hy) return 0;
if(a+1==hx && b+2 ==hy) return 0;
if(a-1==hx && b+2==hy) return 0;
if(a-2==hx && b+1==hy) return 0;
if(a-2==hx && b-1==hy) return 0;
if(a-1==hx && b-2==hy) return 0;
if(a+1==hx && b-2==hy) return 0;
if(a+2==hx && b-1==hy) return 0;
return 1;
}
void dfs(int a,int b)
{
if(a==m && b==n)
{
ans++;
return;
}
if(a<m && choose(a+1,b)) dfs(a+1,b);
if(b<n && choose(a,b+1)) dfs(a,b+1);
return;
}
int main()
{
cin>>m>>n>>hx>>hy;
dfs(0,0);
cout<<ans<<endl;
return 0;
}

1 条评论

  • 1

信息

ID
1121
难度
4
分类
动态规划 点击显示
标签
递交数
9583
已通过
3786
通过率
40%
被复制
25
上传者