搜索
简帛阁>技术文章>一本通1314:过河卒(Noip2002)

一本通1314:过河卒(Noip2002)

1314:【例3.6】过河卒(Noip2002)


时间限制: 1000 ms         内存限制: 65536 KB
提交数: 22768     通过数: 9776

【题目描述】

棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上的某一点有一个对方的马(如C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点,如图3-1中的C点和P1,……,P8,卒不能通过对方马的控制点。棋盘用坐标表示,A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的,C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。

【输入】

class="xxbox">

给出n、m和C点的坐标。

【输出】

从A点能够到达B点的路径的条数。

【输入样例】

8 6 0 4

【输出样例】

1617
代码如下:
#include<iostream>
#include<stdio.h>
using namespace std;
long long f[21][21]={0},g[21][21]={0};
int main()
{
    int n,m,cx,cy,i,j;
    scanf("%d %d %d %d",&n,&m,&cx,&cy);
    f[0][0]=1;//初始化出发点 
    g[cx][cy]=1;//标注C点
    //判断C可走的点是否越界 并标注 
    if(cx-2>=0&&cy-1>=0)g[cx-2][cy-1]=1; 
    if(cx-1>=0&&cy-2>=0)g[cx-1][cy-2]=1; 
    if(cx+1<=n&&cy-2>=0)g[cx+1][cy-2]=1; 
    if(cx+2<=n&&cy-1>=0)g[cx+2][cy-1]=1; 
    if(cx+2<=n&&cy+1<=m)g[cx+2][cy+1]=1; 
    if(cx+1<=n&&cy+2<=m)g[cx+1][cy+2]=1; 
    if(cx-1>=0&&cy+2<=m)g[cx-1][cy+2]=1; 
    if(cx-2>=0&&cy+1<=m)g[cx-2][cy+1]=1; 
    //初始化边界 
    for(i=1;i<=n;i++)
        if(g[i][0]==0) f[i][0]=f[i-1][0];
    for(i=1;i<=m;i++)
        if(g[0][i]==0) f[0][i]=f[0][i-1];
    //逐层递推 
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            if(g[i][j]==1)f[i][j]=0;
            if(g[i][j]==0)f[i][j]=f[i-1][j]+f[i][j-1];
        }    
    printf("%lld",f[n][m]);
    return 0;
}

 

1314:【例36】过河(Noip2002)时间限制:1000ms内存限制:65536KB提交数:22768通过数:9776【题目描述】棋盘上A点有一个过河,需要走到目标B点。行走的规则:可以
【问题描述】有n堆纸牌,编号分别为1,2,…,n。每堆上有若干张,但纸牌总数必为n的倍数。可以在任一堆上取若于张纸牌,然后移动。移牌规则为:在编号为1堆上取的纸牌,只能移到编号为2的堆上;在编号为n的
已知:Sn1+1/2+1/3+…+1/n。显然对于任意一个整数k,当n足够大的时候,Sn>k。现给出一个整数k,要求计算出一个最小的n,使得Sn>k。输入格式一个正整数k。输出格式一个正整
题目传送门这道题目没有什么难的,是一道拓扑排序+递推的题目。我的思路是开始处理出拓扑序,然后因为数据范围很小怎么搞都可以,就邻接矩阵存图+暴力枚举。结果60分。后来看题解发现,大家都是边拓扑边进行递推
题目链接:https://acnowcodercom/acm/contest/230/B题目大意:略分析:DFS模板题。代码如下:1include<bits/stdc++h>2usingn
1模拟这种做法的思路是枚举nn从1开始,直到Sn>kSn>k结束,只需要一个循环即可实现。define_CRT_SECURE_NO_WARNINGSinclude<stdioh>intma
题目里给的范围是k<4,但是官方数据并没有k4的情况,导致一些奇奇怪怪的DP写法也能过。听说标程在k4的时候有反例,掀桌…难怪COGS上k4的数据答案是错的。还是好好写个搜索吧:网上写法很多我是
【算法】状态压缩型DP【题解】Qtx+(t1)y对于Q≥t(t1),x,y一定有解。所以当两石子间距离long>t(t1)时,令longt(t1),重新构造数组即可。【注意】1输入的石子位置无序
f(i,j)f(i1,j)+f(i,j1),显然可以暴力递归求解,但是很多重复的状态,所以可以记忆下来。注意障碍点和边界的特判。1include<cstdio>2include<cs
1414:【17NOIP普及组】成绩时间限制:1000ms内存限制:65536KB提交数:21156通过数:11961【题目描述】牛牛最近学习了C++入门课程,这门课程的总成绩计算方法是:总成绩作业成