#include<bits/stdc++.h> using namespace std; long long int map1[40][40]; int map2[40][40]; int mx,my,endx,endy; int step1[8][2]={{1,2},{2,1},{-1,2},{2,-1},{-2,1},{1,-2},{-1,-2},{-2,-1}}; void stepm(int a,int b); int main() { cin>>endx>>endy>>mx>>my; endx += 2; endy += 2; mx += 2; my += 2; map2[mx][my]=1; stepm(mx,my); int i,j; map1[2][1] = 1; for(i = 2;i <= endx;i++) { for(j = 2;j <= endy;j++) { if(map2[i][j]==1) continue; map1[i][j]=map1[i-1][j]+map1[i][j-1]; } } cout<<map1[endx][endy]; // printf("%lld",map1[endx][endy]); } void stepm(int a,int b) { int i; int nx,ny; for(i = 0;i <= 7;i++) { nx = a + step1[i][0]; ny = b + step1[i][1]; if(nx <= endx && nx>=0 && ny<= endy && ny >=0 && (nx != 0 || ny !=0)&&(nx!=endx ||ny != endy)) map2[nx][ny] = 1; } }
过河卒,比较经典的一道dp题,第一次思路没对,超时,用的dfs,感觉还是有些过于执着写模板,希望能早点改一下这种习惯。