Description
如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。
棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，，同样马的位置坐标是需要给出的（约定: C<>A，同时C<>B）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。
Input
键盘输入B点的坐标（n,m）以及对方马的坐标（X,Y）{不用判错}
Output
屏幕输出一个整数（路径的条数）。
Sample Input
6 6 3 2
Sample Output
17
Source
NOIP2002
题解思路：：由于刚刚学过dfs，就很自然的想到了用dfs来做，但是一个很严重的问题就是时间复杂度用dfs的时间复杂度是n! 20! =2432902008176640000，就算是剪枝也做不来。今天又看到这个题目，发现这是一道经典的dp题，状态转移方程为dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i ][ j – 1 ],只要把（0,0）的位置的dp设置为1，把马占去的位置的 dp 设置为0，问题迎刃而解。
为了避免判断各种情况，我把（0，0）坐标移到（3,3）把dp数组开到28.
代码：：#include <iostream>#include <sstream>#include <ios>#include <iomanip>#include <functional>#include <algorithm>#include <vector>#include <string>#include <list>#include <queue>#include <deque>#include <stack>#include <set>#include <map>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <climits>#include <cctype>#define INF 0x3f3f3f3f#define MP(X,Y) make_pair(X,Y)#define PB(X) push_back(X)#define REP(X,N) for(int X=0;X<N;X++)#define REP2(X,L,R) for(int X=L;X<=R;X++)#define DEP(X,R,L) for(int X=R;X>=L;X–)#define CLR(A,X) memset(A,X,sizeof(A))#define IT iterator#define M_PI 3.14159265358979323846#define _ ios_base::sync_with_stdio(0);cin.tie(0);#define X first#define Y second#define MAX_V 10101//#define maxn 10#define lowbit(X) (X & (-X))#include<ctime>using namespace std;typedef long long ll;typedef pair<int,int>PII;typedef pair<PII,int>PPI;/********************************************************************头文件**********************************************************************/ll n,m,X,Y;ll dir[9][2]={{0,0},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};ll dp[28][28];int main(){cin>>n>>m>>X>>Y;memset(dp,0,sizeof(dp));dp[3][3]=1;REP2(i,3,n+3){REP2(j,3,m+3){REP(k,9){dp[X+dir[k][0]+3][Y+dir[k][1]+3] = 0;}dp[i][j] = dp[i-1][j]+dp[i][j-1];dp[3][3] = 1;}}cout<<dp[n+3][m+3]<<endl;return 0;}
版权声明：大家随意浏览。
每一幢房子都有一种不同的颜色，
