题解 P1002 【过河卒】
标数法
这题让我不禁想起了小学奥数的标数法
| A | ||
|---|---|---|
| 水 | ||
| B |
只能往右或往下走，不能走水，请问从A到B有几种走法?
我们都会这样做：
| 1 | 1 | 1 |
|---|---|---|
| 1 | 2 | 3 |
| 1 | 0 | 3 |
| 1 | 1 | 4 |
| 1 | 2 | 6 |
所以共六种走法，这是因为只能往右或往下走，所以每一个格子的走法数，都是上面一个格子加上左边一个格子。
显然，我们已经找到了转移方程
map[i][j]=map[i-1][j]+map[i][j-1];另外，所有不能经过的格子，我们都要标零
因为马走日，所以我们要将9个格子都标零：
!((i==x+2&&j==y+1)||(i==x+2&&j==y-1)||(i==x+1&&j==y+2)||(i==x+1&&j==y-2)||(i==x-1&&j==y+2)||(i==x-1&&j==y-2)||(i==x-2&&j==y+1)||(i==x-2&&j==y-1)||(i==x&&j==y))（特别长对吧）这样我们就能判断是不是马的占领点
然后一行一行的标数：
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!((i==x+2&&j==y+1)||(i==x+2&&j==y-1)||(i==x+1&&j==y+2)||(i==x+1&&j==y-2)||(i==x-1&&j==y+2)||(i==x-1&&j==y-2)||(i==x-2&&j==y+1)||(i==x-2&&j==y-1)||(i==x&&j==y)))
map[i][j]=map[i-1][j]+map[i][j-1];| 最后就是这样： | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 0 | 1 | 0 | 1 | 2 | |
| 1 | 0 | 0 | 1 | 1 | 0 | 2 | |
| 1 | 1 | 1 | 0 | 1 | 1 | 3 | |
| 1 | 0 | 1 | 1 | 2 | 0 | 3 | |
| 1 | 1 | 0 | 1 | 0 | 0 | 3 | |
| 1 | 2 | 2 | 3 | 3 | 3 | 6 |
非常容易 上完整代码（就不加注释了~ 。~）
#include<iostream>
#include<cstring>
using namespace std;
int x,y,m,n;
long long map[25][26];
int main(){
cin>>n>>m>>x>>y;
m++,n++,x++,y++;
memset(map,0,sizeof(map));
map[1][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!((i==x+2&&j==y+1)||(i==x+2&&j==y-1)||(i==x+1&&j==y+2)||(i==x+1&&j==y-2)||(i==x-1&&j==y+2)||(i==x-1&&j==y-2)||(i==x-2&&j==y+1)||(i==x-2&&j==y-1)||(i==x&&j==y)))
map[i][j]=map[i-1][j]+map[i][j-1];
// cout<<'1'<<endl;
cout<<map[n][m];
return 233;
}
//((i != x+2&&j != y+1)&&(i != x+2&&j != y-1)&&(i != x+1&&j != y+2)&&(i != x+1&&j != y-2)&&(i != x-1&&j != y+2)&&(i != x-1&&j != y-2)&&(i != x-2&&j != y+1)&&(i != x-2&&j != y-1)&&(i != x&&j != y))