Checkerboard

56 阅读 0 评论 37 点赞

我是靠谱客的博主大气小伙，最近开发中收集的这篇文章主要介绍Checkerboard，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Byung is playing a game on her infinite checkerboard. The goal of the game is to move from a starting position (rs, cs) to a target position (rt, ct) using exactly x moves, where x is determined by a roll of a N-sided dice.

A move consists in going from a square on the checkerboard to one of its four neighbors - up, down, left or right.

Her dice is unbiased, meaning that every number from 1 to N has the same probability of being rolled.

She's interested in knowing what's the number of different rolls that allow her to move to the target position in the last move. She can move to the same square more than once if she needs to. Can you help her?

Input

The input is composed by a single line containing 5 integers N (1 ≤ N ≤ 109), rs, cs, rt and ct ( - 109 ≤ rs, cs, rt, ct ≤ 109) indicating respectively the number of sides of the dice, the coordinates of the starting position and the coordinates of the target position.

Output

An integer number indicating the number of outcomes that she'll get a good roll.

最小步数移动到目标后，其他正好到达目标点的步数为当前最小步数加2的倍数。

#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    int a, b, c, d, n;
    cin>>n>>a>>b>>c>>d;
    ll sum = (ll)(a-c > 0 ? a-c : c-a) + (b-d > 0 ? b - d: d - b);//计算时必须转换成long long 类型， 加合会超出int
    if(sum > n)
    {
        cout<<0<<endl;
    }
    else if(sum==0)
    {
        cout<<(n>>1)<<endl;
    }
    else
    {
        cout<<((n-sum)>>1)+1<<endl;
    }
    return 0;
}