首页 > 代码库 > CodeVS 1010 过河卒
CodeVS 1010 过河卒
1010 过河卒
2002年NOIP全国联赛普及组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 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 点的路径的条数。
1<=n,m<=15
输入描述 Input Description
键盘输入
B点的坐标（n,m）以及对方马的坐标（X,Y）{不用判错}
输出描述 Output Description
屏幕输出
一个整数（路径的条数）。
样例输入 Sample Input
6 6 3 2
样例输出 Sample Output
17
数据范围及提示 Data Size & Hint
如描述
解题：简单dp
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 20;18 int n,m,x,y;19 bool vis[maxn][maxn];20 int dp[maxn][maxn];21 const int dir[8][2] = {2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1};22 bool isIn(int x,int y){23 return x <= n && x >= 0 && y <= m && y >= 0;24 }25 int main() {26 while(~scanf("%d %d %d %d",&n,&m,&x,&y)){27 memset(vis,false,sizeof(vis));28 vis[x][y] = true;29 for(int i = 0; i < 8; ++i){30 int tx = x+dir[i][0];31 int ty = y+dir[i][1];32 if(isIn(tx,ty)) vis[tx][ty] = true;33 }34 memset(dp,0,sizeof(dp));35 dp[0][0] = 1;36 for(int i = 1; i <= m; ++i) {37 if(vis[0][i]) continue;38 dp[0][i] += dp[0][i-1];39 }40 for(int i = 1; i <= n; ++i){41 if(vis[i][0]) continue;42 dp[i][0] += dp[i-1][0];43 }44 for(int i = 1; i <= n; ++i){45 for(int j = 1; j <= m; ++j){46 if(vis[i][j]) continue;47 dp[i][j] += dp[i-1][j] + dp[i][j-1];48 }49 }50 cout<<dp[n][m]<<endl;51 }52 return 0;53 }
CodeVS 1010 过河卒
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。