洛谷100題チャレンジ (5/100)

P1002 [NOIP2002 普及組] 馬避け - 洛谷 | コンピュータ科学教育新生態

long long型を使用しないと問題発生注意!!!

馬の制御点を全てマークし、残りは通常通り转移すればよい

\(dp[i][j] += dp[i - 1][j] + dp[i][j - 1]\)

\(i=0||j=0\)の場合、左または上からのみ转移可能

using i64 = long long;

using namespace std;

typedef pair Pair;

i64 table[24][24];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int dirX[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
    int dirY[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};

    int targetX, targetY, horseX, horseY;
    cin >> targetX >> targetY >> horseX >> horseY;

    vector blocked(24, vector(24, false));
    for (int k = 0; k < 9; k ++) {
        int nx = dirX[k] + horseX;
        int ny = dirY[k] + horseY;
        if (nx >= 0 && ny >= 0 && nx  startY[i] >> width[i] >> height[i];

    int queryX, queryY;
    cin >> queryX >> queryY;

    int result = 0;
    for (int i = 0; i < n; i ++) {
        if (queryX >= startX[i] && queryY >= startY[i] 
            && queryX