UC知道这题马拦过河卒思路是怎么的？
来源：百度知道 编辑：UC知道 时间：2024/06/08 08:31:49
#include <iostream>
using namespace std;
bool safe(int x,int y,int a,int b)
{
if (abs(x-a)*abs(y-b)==2||abs(x-a)+abs(y-b)==0)
return false;
else
return true;
}
main()
{
int a,b,x,y,i,j;
long long f[30][30];
memset(f,0,sizeof(f));
f[0][0]=1;
cin>>a>>b>>x>>y;
for (i=1;i<=a && safe(x,y,i,0);i++) f[i][0]=1;
for (j=1;j<=b && safe(x,y,0,j);j++) f[0][j]=1;
for (i=1;i<=a;i++)
for (j=1;j<=b;j++)
if (safe(x,y,i,j))
f[i][j]=f[i-1][j]+f[i][j-1];
cout<<f[a][b]<<endl;
system("pause");
return 0;
}
应该怎么分析？
看似简单实际难啊
using namespace std;
bool safe(int x,int y,int a,int b)
{
if (abs(x-a)*abs(y-b)==2||abs(x-a)+abs(y-b)==0)
return false;
else
return true;
}
main()
{
int a,b,x,y,i,j;
long long f[30][30];
memset(f,0,sizeof(f));
f[0][0]=1;
cin>>a>>b>>x>>y;
for (i=1;i<=a && safe(x,y,i,0);i++) f[i][0]=1;
for (j=1;j<=b && safe(x,y,0,j);j++) f[0][j]=1;
for (i=1;i<=a;i++)
for (j=1;j<=b;j++)
if (safe(x,y,i,j))
f[i][j]=f[i-1][j]+f[i][j-1];
cout<<f[a][b]<<endl;
system("pause");
return 0;
}
应该怎么分析？
看似简单实际难啊
递推
f[i][j]=f[i-1][j]+f[i][j-1]表示卒在(i,j)是从左边或者上边走到的，那卒到(i,j)有几种走法当然是 左边和上边的走法数相加了。
for (i=1;i<=a && safe(x,y,i,0);i++) f[i][0]=1;
for (j=1;j<=b && safe(x,y,0,j);j++) f[0][j]=1;
这两句是边缘的情况处理，因为边缘的点只能由一个方向走到。
safe函数看2楼的解释，非常详细。
以后碰到这种题，想想它前后的联系，就是它怎么到达这点的，自然迎刃而解了
...a,b,x,y,i,j...可以说明一下吗？
悲哀...
像看密码，看半天也看不懂x,y,a,b…大概是兵和马的位置吧，怎么表示不明白。
if(abs(x-a)*abs(y-b)==2||abs(x-a)+abs(y-b)==0)
这句是判断兵是否安全的，不安全return false;安全return true;
其中abs(x-a)*abs(y-b)==2是判断兵和马的相对位置是否是斜日，因为等于2时abs(x-a)和abs(y-b)一个取1值，一个取2值，正好是斜日，兵不安全。
abs(x-a)+abs(y-b)==0时好解，两个都是0值，兵马在一个位置，兵被吃了。
因为没弄清x,y,a,b怎么表示兵马的位置，所以数组f又是怎么存结果的我也搞不清了。