- 马拦过河卒
- 2016-04-24 17:45:47 @
今天下午第二题,难度不难,因为数据小,用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 条评论
-
少女夜夜 LV 9 MOD @ 2016-04-24 20:26:06
请在题解区域 [https://vijos.org/p/1121/solution] 发布题解。
- 1