【回溯法】马拦过河卒_动态规划
<center>
提交: 43 解决: 13
[提交][状态][讨论版] </center> 
View Code
问题 I: 【回溯法】马拦过河卒
时间限制: 1 Sec 内存限制: 128 MB提交: 43 解决: 13
[提交][状态][讨论版] </center>
题目描述
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过20的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过20的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入
一行四个数据，分别表示B点坐标和马的坐标。（保证所有的数据有解）
输出
一个数据，表示所有的路径条数。
样例输入
6 6 3 3 样例输出
6
upc上好像测试数据有问题，写的是到20，别的网站都是到15，到二十回溯法肯定会超时啊，别的做的是不是都是用动态规划递推做的。
去别的网站提交AC。
代码：
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 int n,m; 7 int c=0; 8 int horse_x,horse_y; 9 int a[25][25]={0};//值为0可以走，为1不可走 10 int cou[25][25]={0};//记录到这一坐标的所有的路径条数 11 12 void horse_location(){ 13 int x[8]={-2,-1,1,2,2,1,-1,-2}; 14 int y[8]={1,2,2,1,-1,-2,-2,-1}; 15 a[horse_x+1][horse_y+1]=1; 16 for(int i=0;i<8;i++){ 17 int new_x=horse_x+x[i]+1; 18 int new_y=horse_y+y[i]+1; 19 if(new_x>=1&&new_y<=n+1&&new_y>=1&&new_y<=m+1){ 20 a[horse_x+x[i]+1][horse_y+y[i]+1]=1; 21 } 22 } 23 } 24 25 void backtrack(int x,int y){ 26 int xx[2]={0,1}; 27 int yy[2]={1,0}; 28 if(x==n+1&&y==m+1){ 29 c++; 30 return ; 31 } 32 for(int i=0;i<2;i++){ 33 if(a[x+xx[i]][y+yy[i]]==0){ 34 backtrack(x+xx[i],y+yy[i]); 35 } 36 } 37 } 38 39 int main() 40 { 41 scanf("%d %d %d %d",&n,&m,&horse_x,&horse_y); 42 horse_location(); 43 for(int i=1;i<=m+2;i++){ 44 a[n+2][i]=1; 45 } 46 for(int i=1;i<=n+2;i++){ 47 a[i][m+2]=1; 48 } 49 backtrack(1,1); 50 printf("%d",c); 51 return 0; 52 }
------2016_08_09-------
然后又用动态规划做了一遍，出了点小错误，死活不对，最后发现应该把数组开成long int。而不是int！
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 int n,m; 8 int horse_x,horse_y; 9 long int cou[55][55]={0};//记录到这一坐标的所有的路径条数 10 11 void horse_location(){ 12 int x[8]={-2,-1,1,2,2,1,-1,-2}; 13 int y[8]={1,2,2,1,-1,-2,-2,-1}; 14 cou[horse_x+1][horse_y+1]=0; 15 for(int i=0;i<8;i++){ 16 int new_x=horse_x+x[i]+1; 17 int new_y=horse_y+y[i]+1; 18 if(new_x>=0&&new_y>=0){ 19 //if(new_x==1&&new_y==1||new_x==n+1&&new_y==m+1){ 20 // continue; 21 //} 22 cou[new_x][new_y]=0; 23 } 24 } 25 } 26 27 void DP(){ 28 for(int i=1;i<=n+1;i++){ 29 for(int j=1;j<=m+1;j++){ 30 if(i==1&&j==1) continue; 31 if(cou[i][j]==-1){ 32 cou[i][j]=cou[i-1][j]+cou[i][j-1]; 33 } 34 } 35 } 36 } 37 38 int main() 39 { 40 scanf("%d %d %d %d",&n,&m,&horse_x,&horse_y); 41 memset(cou,-1,sizeof(cou)); 42 horse_location(); 43 for(int i=0;i<=m+1;i++){ 44 cou[0][i]=0; 45 } 46 for(int i=0;i<=n+1;i++){ 47 cou[i][0]=0; 48 } 49 cou[1][1]=1; 50 DP(); 51 printf("%ld",cou[n+1][m+1]); 52 return 0; 53 }
阿里巴巴公司氛围 330人发布