过河卒 - sherlockyk - 博客园
过河卒 Time Limit:1000MS Memory Limit:65536K 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年第八届全国青少年信息学奥林匹克分区联赛复赛普及组试题4 1 //动态规划2 #include<cstdio>3 #include<cstring>4 #include<iostream>5 #include<cmath>6 using namespace std;7 8 int main(){9 int n,m,nn,mm,i,j; 10 long long f[100][100]; 11 cin>>n>>m>>nn>>mm; 12 nn++;mm++;n++;m++; 13 memset(f,0,sizeof(f));f[0][1]=1; 14 for(i=1;i<=n;i++) 15 for(j=1;j<=m;j++) 16 if((abs(i-nn)+abs(j-mm)==3)&&(i!=nn)&&(j!=mm)||(i==nn&&j==mm)); 17 else f[i][j]=f[i-1][j]+f[i][j-1]; 18 cout<<f[n][m]; 19 return 0; 20 }
过河卒（递推和递归） - py佐料 - 博客园
过河卒（递推和递归）#include <iostream> #include <cstdio> using namespace std; int d[25][25],n,m,cx,cy; long long dp[25][25]; //d数组用来记录是不是控制点（“马点”），dp数组用来记录路径数 int dir[8][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}}; //二维方向数组（将“马点”全部标记为1） //dp[n][m]就表示到坐标为(n,m)点的可能的路径总数 void fun() { d[cx][cy]=1; //马的初始位置（有马的地方标记为1） for(int i=0;i<8;i++) { int tx=cx+dir[i][0]; int ty=cy+dir[i][1]; if(tx>=0 && tx<=n && ty>=0 && ty<=m) //注意范围 d[tx][ty]=1; //有马的地方标记为1 } dp[0][0]=1; //不能把做这样的初始化：dp[1][0]=1; dp[0][1]=1;的原因在于：这两个点可能是“马点” for(int i=0;i<=n;i++) //取等，因为需要算到坐标（n，m） { for(int j=0;j<=m;j++)//取等，因为需要算到坐标（n，m） { if(d[i][j]==0)//有马的地方不去（所以直接不算入） { if(i!=0 && j!=0) dp[i][j]+=dp[i][j-1]+dp[i-1][j];//左边或者上边有马时，这一边过来的方法按0计算（所以这里直接加就行，因为数组的初始化是0） if(i==0) //马只能往右或者往下 dp[i][j]+=dp[i][j-1]; //第一次循环时j-1是-1，没关系，反正dp初始化都是0 if(j==0) dp[i][j]+=dp[i-1][j]; } } } cout<<dp[n][m]; } int main() { cin>>n>>m; cin>>cx>>cy; fun(); return 0; }这篇文章，是又一个故事的结束... lazy's story is continuing. posted @ 2020-08-28 11:26 py佐料 阅读(458) 评论(0) 编辑 收藏 举报
过河卒 - 单身贵族1123 - 博客园
例3.6】过河卒(Noip2002) 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的某一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n,m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。【输入】 给出n、m和C点的坐标。#include <stdio.h> int main() {int i,j,dx[8]={2,1,-1,-2,-2,-1,1,2},dy[8]={1,2,2,1,-1,-2,-2,-1};int n,m,x,y;long long a[32][32]={0};scanf("%d%d%d%d",&n,&m,&x,&y);a[x][y]=-1,a[0][0]=1;for(i=0;i<8;i++)if((x+dx[i])>=0&&(x+dx[i])<=n&&(y+dy[i])>=0&&(y+dy[i])<=m){a[x+dx[i]][(y+dy[i])]=-1;}for(i=1;i<=m;i++){//处理第一行 if(a[0][i]==-1)a[0][i]=0;else a[0][i]=a[0][i-1];}for(i=1;i<=n;i++){//处理第一列 if(a[i][0]==-1)a[i][0]=0;else a[i][0]=a[i-1][0];}for(i=1;i<=n;i++)//处理剩下的 for(j=1;j<=m;j++){if(a[i][j]==-1)a[i][j]=0;else a[i][j]=a[i-1][j]+a[i][j-1];}/* for(i=0;i<=n;i++){for(j=0;j<=m;j++)printf("%5d",a[i][j]);putchar(' ');}*/printf("%ld ",a[n][m]);return 0; } 【输出】 从A点能够到达B点的路径的条数。 【输入样例】8 6 0 4【输出样例】1617
