P1002[过河卒]题解

Suica_Dein · 2021-08-22 11:30:55 · 个人记录

前言

这道题不难,普及-的难度 但是我被坑了一下T_T

主要思路

这道题主要用了一个递推的思路,用一个二维数组来实现(我的二维数组名叫map) ,题目中说坐标是从(0,0)到(n,m),为了避免数组越界,就将从(0,0)到(n,m)变为从(1,1)到(n + 1,m + 1) (就是坐标值增加1),再用for循环将map(0,0),map(0,1)...map(0, m)和map(1,0),map(2,0)...map(n,0)设为0,再将马的坐标以及马能影响的坐标的值设为0。并且将map(1, 1)设为1,之后for循环开始递推,递推关系式为:

遇到马的坐标以及马能影响的坐标时continue掉,最后输出map(n,m)即可! (加1后的n,m)

60分做法(部分分)

于是你信心十足地开始写代码!

#include <iostream>
#include <cstring>
using namespace std;
int map[30][30];
int main()
{
    memset(map,1,sizeof(map));
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    x++; y++; n++; m++;
    map[x][y] = 0;
    map[x - 1][y - 2] = 0;
    map[x + 1][y - 2] = 0;
    map[x + 2][y - 1] = 0;
    map[x + 2][y + 1] = 0;
    map[x + 1][y + 2] = 0;
    map[x - 1][y + 2] = 0;
    map[x - 2][y - 1] = 0;
    map[x - 2][y + 1] = 0;
    for (int i = 0; i <= m; i++)
    {
        map[0][i] = 0;
    }
    for (int i = 0; i <= n; i++)
    {
        map[i][0] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (map[i][j] == 0) continue;
            else if (i == 1 && j == 1) map[i][j] = 1;
            else map[i][j] = map[i - 1][j] + map[i][j - 1];
        }
    }
    cout << map[n][m] << endl;
    return 0;   
}

恭喜你!
.
.
.
.
.
你得到了60分! 但是我们要的是100分,是AC,并不是部分分!

为什么没AC?

我们来看我们的递推公式:

根据递推公式,我们可知:(在没马的情况下)

这个增长速度是非常快的!
我们看题目的限制条件