A knight jumps around an infinite chessboard. The chessboard is an unexplored territory. In the spirit of explorers, whoever stands on a square for the first time claims the ownership of this square. The knight initially owns the square he stands, and jumps $N$ times before he gets bored. Recall that a knight can jump in 8 directions. Each direction consists of two squares forward and then one squaure sidways.

After $N$ jumps, how many squares can possibly be claimed as territory of the knight? As $N$ can be really large, this becomes a nightmare to the knight who is not very good at math. Can you help to answer this question?


The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
Each test case contains only one number $N$, indicating how many times the knight jumps.
$1 \leq T \leq 10^5$,$0 \leq N \leq 10^9$


For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of squares that can possibly be claimed by the knight.

#source 2017 CCPC FINAL

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
// 打表推公式
int a[]={1,9,41,109,205,325,473};
int main() {
    int t;scanf("%d", &t);
    for(int kase=1; kase<=t; kase++){
        ll n;scanf("%lld", &n);
        printf("Case #%d: ", kase);
        if(n<=6) {
        printf("%llu\n",176 * (n-6) + (n-6) * (n-7) * 14 + 473);
    return 0;
int dir[][2]={{-2,1},{-1,2},{1,2},{2,1},{1,-2},{2,-1},{-2,-1},{-1,-2}};
struct node{
    int x, y, steps;
const int maxn = 1111;
int ans[maxn];
bool vis[maxn][maxn];
void bfs() {
    queue<node> q;
    ans[0] = 1;
    vis[500][500] = 1;
        node cur = q.front(); q.pop();
        if(cur.steps == 20) continue;
        for(int i=0; i<8; i++){
            node nxt = cur;
            nxt.x += dir[i][0], nxt.y += dir[i][1];
            if(vis[nxt.x][nxt.y]) continue;
            vis[nxt.x][nxt.y] = 1;
            ans[++nxt.steps] ++;
int main() {
    bfs(); int ret = 0;
    for(int i=0;i<=20;i++) printf("%d ", ans[i]);puts("");
    for(int i=0;i<20;i++) printf("%d ", (ret+=ans[i])); puts("");
    for(int i=1;i<20;i++) printf("%d ",ans[i]-ans[i-1]);
    for(int i=7;i<=20;i++) printf("%d ",176 * (i-6) + (i-6) * (i-7) / 2 * 28 + 473);
分类: ACM


电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.