惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

博客园_首页
I
InfoQ
The Register - Security
The Register - Security
L
LangChain Blog
H
Help Net Security
The GitHub Blog
The GitHub Blog
S
Schneier on Security
博客园 - 【当耐特】
W
WeLiveSecurity
Attack and Defense Labs
Attack and Defense Labs
IT之家
IT之家
CTFtime.org: upcoming CTF events
CTFtime.org: upcoming CTF events
Google DeepMind News
Google DeepMind News
The Cloudflare Blog
H
Heimdal Security Blog
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
Y
Y Combinator Blog
雷峰网
雷峰网
N
Netflix TechBlog - Medium
Security Archives - TechRepublic
Security Archives - TechRepublic
cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
L
Lohrmann on Cybersecurity
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
T
The Exploit Database - CXSecurity.com
P
Privacy & Cybersecurity Law Blog
G
GRAHAM CLULEY
Exploit-DB.com RSS Feed
Exploit-DB.com RSS Feed
V
Visual Studio Blog
博客园 - 聂微东
PCI Perspectives
PCI Perspectives
Last Week in AI
Last Week in AI
A
Arctic Wolf
宝玉的分享
宝玉的分享
T
The Blog of Author Tim Ferriss
S
Secure Thoughts
T
Threat Research - Cisco Blogs
GbyAI
GbyAI
云风的 BLOG
云风的 BLOG
D
Darknet – Hacking Tools, Hacker News & Cyber Security
S
SegmentFault 最新的问题
SecWiki News
SecWiki News
月光博客
月光博客
大猫的无限游戏
大猫的无限游戏
Schneier on Security
Schneier on Security
P
Proofpoint News Feed
博客园 - Franky
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
AI
AI
Engineering at Meta
Engineering at Meta

博客园 - NOIP/NOI辅导

ubuntu下查看(改变)本地端口开放情况,开启和关闭防火墙 [NOIP] - CCF NOIP2018普及组初赛试题+答案 [NOIP] - 阶乘之和 [NOIP题目] - 方格取数 [NOIP题目] - 铺地毯 [NOI题目] - 抽签 中小学阶段,学习NOIP信息学有用吗? [信息学奥赛] NOI2018冬令营获奖名单 信息学奥赛介绍 五大学科竞赛 从哪个年级学习信息学奥赛好呢? NOI-001 —《C++编程及竞赛训练》 NOI-002 —《普及组竞赛强化训练课程》 NOI-003 —《初级算法课程》 [iOS] 解决Xcode rename failed的问题 [Android] - Android Studio 执行Log.v和Log.d 不显示打印 [Git] 403 error [React-Native] RelativeLayout是相对布局控件 - 转 [Android] 代码中动态设置shape
[NOIP题目] - 马拦过河卒
NOIP/NOI辅导 · 2018-09-24 · via 博客园 - NOIP/NOI辅导

题干

棋盘上AA点有一个过河卒,需要走到目标BB点。卒行走的规则:可以向下、或者向右。同时在棋盘上CC点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示,A点(0, 0)、B点(n,m)(n, m为不超过20的整数),同样马的位置坐标是需要给出的。

现在要求你计算出卒从A点能够到达B点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

输入输出格式
输入格式:
一行四个数据,分别表示B点坐标和马的坐标。

输出格式:
一个数据,表示所有的路径条数。
输入样例 输出样例
6 6 3 3(注:空格分隔) 6

分析:
1、正常情况下,通过一个点路径条数的算法
如果不考虑马的因素,那么卒子线路中所经过的一个点,可以来自于两个点,即此点正上方的点和左方的点,那么通过此点的路径数量即为:正上方的点的路径数量 + 左方的点的路径数量(公式:f[n,m] = f[n, m -1] + f[n - 1, m])。
2、特殊情况1,马的情况
3、最上边界和最左边界
如不考虑马的情况,那么最上边界和最左边界上的点只是1。

代码:

//
//  main.cpp
//  AdvancedPawn
//
//  Created on 2018/9/23.
//  Copyright © 2018. All rights reserved.
//

#include <iostream>
#include<stdio.h>
#include<string.h>



using namespace std;

int f[20][20];
int g[20][20];



int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    
    
    int i, j, n, m, x, y;
    memset(f, 0, sizeof(f)); //清空,数组元素起始值皆为0
    memset(g, 0, sizeof(g));
    scanf("%d %d %d %d", &n, &m, &x, &y); //输入目标点B、马的位置
    f[0][0] = 1; //思考一下为什么出发点的路径数为1,而不是为0
    g[x][y] = 1; //自己偷偷举个小栗子就知道啦^_^
    g[x - 1][y - 2] = 1; g[x - 1][y + 2] = 1; //马的控制点
    g[x + 1][y + 2] = 1; g[x + 1][y - 2] = 1; //第一次做的时候
    g[x - 2][y - 1] = 1; g[x - 2][y + 1] = 1; //1和2傻傻没看清楚
    g[x + 2][y - 1] = 1; g[x + 2][y + 1] = 1; //WA了N次,呜呜~
    for(i = 1; i <= n; i++){ //纵向边界初始化(第一列)
        if(!g[i][0]){
            f[i][0] = 1; //不是马的控制点,该点的路径数设为1
        }
        else{            //否则在边界上此点及之后的点路径数为0
            break;       //思考一下为什么?
        }                //在边界上还可以从哪里到该点?
    }                    //是不是不能了,因为可以来的路被马“截断”了
    for(i = 1; i <= m; i++){ //横向边界初始化(第一行)
        if(!g[0][i]){        //同上,不解释
            f[0][i] = 1;
        }
        else{
            break;
        }
    }                        //一步步递推
    for(i = 1; i <= n; i++){ //本题重要的代码精华部分,模拟从起始点出发,每
        for(j = 1; j <= m; j++){ //一步到达的点的路径数之和
            if(!g[i][j]) //如果不是马的控制点,该点的路径数为左边+上边点的路
                f[i][j] = f[i - 1][j] + f[i][j - 1]; //径数
        }
    }
    printf("%d\n", f[n][m]); //输出所有的路线和
    
    
    
    return 0;
}