马拦过河卒路径计数-csdn博客

题目描述 棋盘上AA点有一个过河卒，需要走到目标BB点。卒行走的规则：可以向下、或者向右。同时在棋盘上CC点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，AA点(0, 0)(0,0)、BB点(n, m)(n,m)(nn, mm为不超过2020的整数)，同样马的位置坐标是需要给出的。 现在要求你计算出卒从AA点能够到达BB点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 输入格式 一行四个数据，分别表示BB点坐标和马的坐标。 输出格式 一个数据，表示所有的路径条数。 输入输出样例 输入 #1 6 6 3 3输出 #1 6说明/提示 结果可能很大！ #include <iostream> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> #include <algorithm> #include <set> #include <map> #include <climits> #include <stdio.h> #include <iomanip> #include <math.h> #include <list> #include <queue> #include <tuple> #include <stack> #include <string.h> using namespace std; #define size 1000long long myarray[size][size];bool isarea(int x1, int y1) {if(x1 < 0 || x1 >= size || y1 < 0 || y1 >= size)return false;return true; } void mysetHorse(int x2, int y2) {myarray[x2][y2] = -1;if(isarea(x2-2,y2-1))myarray[x2-2][y2-1] = -1;if(isarea(x2-2,y2+1))myarray[x2-2][y2+1] = -1;if(isarea(x2-1,y2-2))myarray[x2-1][y2-2] = -1;if(isarea(x2-1,y2+2))myarray[x2-1][y2+2] = -1;if(isarea(x2+1,y2-2))myarray[x2+1][y2-2] = -1;if(isarea(x2+1,y2+2))myarray[x2+1][y2+2] = -1;if(isarea(x2+2,y2-1))myarray[x2+2][y2-1] = -1;if(isarea(x2+2,y2+1))myarray[x2+2][y2+1] = -1; } int main(void) {int x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;mysetHorse(x2,y2);for(int i = 0; i <= x1; i++){for(int j = 0; j <= y1; j++){if(i == 0 && j == 0){myarray[i][j] = 1;}else if(i == 0){if(myarray[i][j] == -1){myarray[i][j] = 0;}elsemyarray[i][j] = myarray[i][j-1];}else if(j == 0){if(myarray[i][j] == -1){myarray[i][j] = 0;}elsemyarray[i][j] = myarray[i-1][j];}else{if(myarray[i][j] == -1){myarray[i][j] = 0;}else{if(isarea(i-1,j)){myarray[i][j] += myarray[i-1][j];}if(isarea(i,j-1))myarray[i][j] += myarray[i][j-1];}}}}// for(int i = 0; i <= x1; i++)// {// for(int j = 0; j <= y1; j++)// {// cout << myarray[i][j]<<" ";// }// cout << endl;// }cout << myarray[x1][y1] << endl;return 0;}

过河卒 - 皮皮嘉 - 博客园

3065: [2002_p4]过河卒 时间限制: 1 Sec  内存限制: 125 MB提交: 12  解决: 5[提交][状态][讨论版][命题人:外部导入][Edit] [TestData] 题目描述如图，A点有一个过河卒，需要走到目标B点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如图中的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如图中C 点上的马可以控制9个点（图中的P1，P2...P8 和C）。卒不能通过对方马的控制点。棋盘用坐标表示，A点（0,0）、B点（n,m）（n，m 为不超过20的整数，并由键盘输入），同样马的位置坐标是需要给出的（约定：C<>A，同时C<>B）。现在要求你计算出卒从A点能够到达B点的路径的条数。  输入每个测试文件只包含一组测试数据，每组输入四个整数n，m，x，y。（（n,m）表示B点的坐标，（x,y）表示对方马的坐标）  输出对于每组输入数据，输出一个整数，表示路径的条数。  样例输入 6 6 3 2 样例输出 17解题思路：开始我是直接暴力搜索，但是超时了，然后优化了一下时间复杂度，采用了记忆化搜索，开一个ans二维数组用于保存每个点到达终点的路径次数，这样当下次搜到这个点时，可以直接得到路径次数。下面分别贴出两次提交的代码：第一次超时：#include<bits/stdc++.h> using namespace std;int hi,hj,ei,ej; int cnt; int dir[2][2]={{0,1},{1,0}};bool check(int a,int b) {if(a>ei||b>ej||(a==hi&&b==hj)||(a==hi-1&&b==hj-2)||(a==hi+1&&b==hj-2)||(a==hi-2&&b==hj-1)||(a==hi+2&&b==hj-1)||(a==hi+1&&b==hj+2)||(a==hi-1&&b==hj+2)||(a==hi+2&&b==hj+1)||(a==hi-2&&b==hj+1))return false;else return true; }void dfs(int x,int y) {if(x==ei&&y==ej){cnt++;return;}for(int i=0;i<2;++i){x+=dir[i][0];y+=dir[i][1];if(check(x,y)){dfs(x,y);}x-=dir[i][0];y-=dir[i][1];} }int main() {while(cin>>ei>>ej>>hi>>hj){cnt=0;dfs(0,0);cout<<cnt<<endl;}return 0; }第二次AC：#include <iostream> #include <cstring> using namespace std;int hi,hj,ei,ej; int cnt; int dir[2][2]={{0,1},{1,0}}; long long ans[21][21];//这里要用longlong，因为当格子数很多的时候，路径会超多的，用int会wa bool check(int a,int b) {if(a>ei||b>ej||(a==hi&&b==hj)||(a==hi-1&&b==hj-2)||(a==hi+1&&b==hj-2)||(a==hi-2&&b==hj-1)||(a==hi+2&&b==hj-1)||(a==hi+1&&b==hj+2)||(a==hi-1&&b==hj+2)||(a==hi+2&&b==hj+1)||(a==hi-2&&b==hj+1))return false;else return true; }long long dfs(int x,int y) {if(ans[x][y]!=-1)return ans[x][y];if(x==ei&&y==ej){cnt++;return 1;}long long res=0;for(int i=0;i<2;++i){x+=dir[i][0];y+=dir[i][1];if(check(x,y)){res+=dfs(x,y);}x-=dir[i][0];y-=dir[i][1];}return ans[x][y]=res;//保存每一个点到终点的路径数 }int main() {while(cin>>ei>>ej>>hi>>hj){memset(ans,-1,sizeof ans);cnt=0;dfs(0,0);cout<<ans[0][0]<<endl;}return 0; } 

过河卒 - gtr

题目描述棋盘上AAA点有一个过河卒，需要走到目标BBB点。卒行走的规则：可以向下、或者向右。同时在棋盘上CCC点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，AAA点(0,0)(0, 0)(0,0)、BBB点(n,m)(n, m)(n,m)(nnn, mmm为不超过202020的整数)，同样马的位置坐标是需要给出的。 现在要求你计算出卒从AAA点能够到达BBB点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。输入格式一行四个数据，分别表示BBB点坐标和马的坐标。输出格式一个数据，表示所有的路径条数。输入输出样例输入 #16 6 3 3输出 #16说明/提示结果可能很大！ 【解题思路】 经典老题，看代码1 #include <iostream> 2 using namespace std; 3 long long x1,y1,x2,y2,p[22][22]; 4 int pan(long long x1,long long y1, long long x2, long long y2) 5 { 6 p[x2][y2]=-1; 7 if (x2+2<=x1&&y2+1<=y1) p[x2+2][y2+1]=-1; 8 if (x2+2<=x1&&y2-1>=1) p[x2+2][y2-1]=-1; 9 if (x2+1<=x1&&y2+2<=y1) p[x2+1][y2+2]=-1; 10 if (x2+1<=x1&&y2-2>=1) p[x2+1][y2-2]=-1; 11 if (x2-1>=1&&y2+2<=y1) p[x2-1][y2+2]=-1; 12 if (x2-1>=1&&y2-2>=1) p[x2-1][y2-2]=-1; 13 if (x2-2>=1&&y2+1<=y1) p[x2-2][y2+1]=-1; 14 if (x2-2>=1&&y2-1>=1) p[x2-2][y2-1]=-1; 15 return 0; 16 } 17 int main() 18 { 19 cin >>x1>>y1>>x2>>y2; 20 x2++; y2++; x1++; y1++; 21 p[1][0]=1; 22 pan(x1,y1,x2,y2); 23 24 for (long long o1=1;o1<=x1;o1++) 25 for (long long o2=1;o2<=y1;o2++) 26 {if (p[o1][o2]==-1)p[o1][o2]++; else p[o1][o2]=p[o1-1][o2]+p[o1][o2-1];} 27 cout <<p[x1][y1]; 28 return 0; 29 }