16哈理工新生赛 A 棋盘村 (dp)

超、凢脫俗 2022-07-14 08:46 135阅读 0赞

题目链接：[点击打开链接][Link 1]

<table> 
 <tbody> 
 <tr> 
 <td>棋盘村</td> 
 </tr> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>Time Limit: 1000 MS</td> 
 <td>Memory Limit: 32768 K</td> 
 </tr> 
 </tbody> 
 </table> 
 <table> 
 <tbody> 
 <tr> 
 <td>Total Submit: 219(72 users)</td> 
 <td>Total Accepted: 71(61 users)</td> 
 <td>Rating: <img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-half2.png" alt=""></td> 
 <td>Special Judge: No</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 <tr> 
 <td>Description</td> 
 </tr> 
 <tr> 
 <td> &nbsp; &nbsp;一名骑着马的强盗闯进了原本平静祥和的棋盘村，为了通知村里的士兵来打败强盗，你必须要通知位于棋盘村最下方的兵营。棋盘村的地形就像是一张棋盘，你所在的位置为A点（0,0），兵营位于棋盘村的右下角B点（n,m）。你每次只能走一步，可以选择向下走，也可以选择向右走。但是强盗所在的位置和强盗的马一次所能跳到的位置是不可以走过去的（强盗的马的移动方法与象棋中的马相同）。请计算出从A点能够走到B点的所有路径条数。 <img alt="" src="http://acm.hrbust.edu.cn/contests/attached/image/20161125/20161125121619_65589.jpg"> </td> 
 </tr> 
 <tr> 
 <td>Input</td> 
 </tr> 
 <tr> 
 <td> 
 <div> 
 首先输入一个整数t，代表有t组测试数据。 
 每组测试数据为四个整数，即B点的坐标（n，m）和强盗的坐标（x，y）。 
 1 &lt; n,m &lt; 20. 
 
 </div> </td> 
 </tr> 
 <tr> 
 <td>Output</td> 
 </tr> 
 <tr> 
 <td> 输出一个整数即路径的条数。 </td> 
 </tr> 
 <tr> 
 <td>Sample Input</td> 
 </tr> 
 <tr> 
 <td> 2 6 6 3 2 8 8 3 5</td> 
 </tr> 
 <tr> 
 <td>Sample Output</td> 
 </tr> 
 <tr> 
 <td> 17 1393</td> 
 </tr> 
 <tr> 
 <td>Source</td> 
 </tr> 
 <tr> 
 <td>2016级新生程序设计全国邀请赛</td> 
 </tr> 
 </tbody> 
</table>

题解：dp。要到达棋盘上的一个点，只能从左边或者上边过来。然后判断马字走法能不能走到那些点就可以了。能就不加，不能就继续加 1.

AC代码：

#include<cstdio>
 #include<algorithm>
 #include<cstring>
 using namespace std;
 
 const int maxn=20;
 int n,m,x,y;
 long long dp[maxn+10][maxn+10];
 
 bool gao(int i,int j)
 {
 if(i>n || j>m)return 0;
 if(i==x && j==y)return 0;
 if(abs(i-x)==2 && abs(j-y)==1)return 0;
 if(abs(i-x)==1 && abs(j-y)==2)return 0;
 return 1;
 }
 int main()
 {
 int i,j,k;
 int t;
 scanf("%d",&t);
 while(t--)
 {
 	 memset(dp,0,sizeof(dp));
 		scanf("%d%d%d%d",&n,&m,&x,&y);
 		dp[0][0]=1;
 		for(i=0;i<=n;i++)
 		for(j=0;j<=m;j++)
 	{
 		if(gao(i+1,j))dp[i+1][j]+=dp[i][j];
 	if(gao(i,j+1))dp[i][j+1]+=dp[i][j];
 	}
 		 printf("%lld\n",dp[n][m]); 
 	}
 
 return 0;
 }

[Link 1]: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2293