ZeroJudge 解題筆記：a672. 00155 - All Squares

作者：王一哲
日期：2026年1月12日


ZeroJudge 題目連結：a672. 00155 - All Squares

解題想法

因為以大小為 $k$ 的正方形頂點向外擴張最大範圍為 $$ k_{max} = k + (k-2) + (k-4) + \dots + 1 = \frac{(k+1)^2}{4} $$ 如果 $(x, y)$ 在四個頂點 $\pm k_{max}$ 以外的範圍，可以不需要再加到堆疊之中，可以少算很多次。

Python 程式碼

使用時間約為 35 ms，記憶體約為 3.4 MB，通過測試。

import sys

def count_squares(k, x, y):  # 輸入大小 k，要找的點座標 (x, y)
    cnt = 0  # (x, y) 被幾個正方形包圍
    st = [(k, 1024, 1024)]  # 要計算的正方形大小、中心位置
    while st:  # 如果 st 還有資料繼續執行
        kc, xc, yc = st.pop()  # 目前的正方形大小、中心位置
        left, right = xc-kc, xc+kc  # 左、右頂點位置
        top, bottom = yc-kc, yc+kc  # 上、下頂點位置
        if left <= x <= right and top <= y <= bottom:  # (x, y) 在這個正方形之中
            cnt += 1  # cnt 加 1
        kn = kc//2  # 下一個正方形的大小
        if kn >= 1:  # 下一個正方形的中心
            kmax = (kc+1)*(kc+1)//4  # 以這個正方形頂點向外擴張的上限，公差為 2 的等差級數
            if left-kmax <= x <= left+kmax and top-kmax <= y <= top+kmax: st.append((kn, left, top))
            if left-kmax <= x <= left+kmax and bottom-kmax <= y <= bottom+kmax: st.append((kn, left, bottom))
            if right-kmax <= x <= right+kmax and top-kmax <= y <= top+kmax: st.append((kn, right, top))
            if right-kmax <= x <= right+kmax and bottom-kmax <= y <= bottom+kmax:st.append((kn, right, bottom))
    return cnt  # 回傳數量

for line in sys.stdin:
    k, x, y = map(int, line.split())
    if k == 0 and x == 0 and y == 0: continue
    print(f"{count_squares(k, x, y):3d}")

C++ 程式碼

使用時間約為 3 ms，記憶體約為 276 kB，通過測試。

#include <cstdio>
#include <stack>
#include <vector>
using namespace std;

int count_squares(int k, int x, int y) {  // 輸入大小 k，要找的點座標 (x, y)
    int cnt = 0;  // (x, y) 被幾個正方形包圍
    stack<vector<int>>st;  // 要計算的正方形大小、中心位置
    st.push({k, 1024, 1024});
    while(!st.empty()) {  // 如果 st 還有資料繼續執行
        auto fir = st.top();  // 取出最後一項
        st.pop();  // 移除最後一項
        int kc = fir[0], xc = fir[1], yc = fir[2]; // 目前的正方形大小、中心位置
        int left = xc-kc, right = xc+kc;  // 左、右頂點位置
        int top = yc-kc, bottom = yc+kc;  // 上、下頂點位置
        if (x >= left && x <= right && y >= top && y <= bottom) cnt++;  // (x, y) 在這個正方形之中 cnt 加 1
        int kn = kc/2;  // 下一個正方形的大小
        if (kn >= 1) {  // 下一個正方形的中心
            int kmax = (kc+1)*(kc+1)/4;  // 以這個正方形頂點向外擴張的上限，公差為 2 的等差級數
            if (x >= left-kmax && x <= left+kmax && y >= top-kmax && y <= top+kmax) st.push({kn, left, top});
            if (x >= left-kmax && x <= left+kmax && y >= bottom-kmax && y <= bottom+kmax) st.push({kn, left, bottom});
            if (x >= right-kmax && x <= right+kmax && y >= top-kmax && y <= top+kmax) st.push({kn, right, top});
            if (x >= right-kmax && x <= right+kmax && y >= bottom-kmax && y <= bottom+kmax) st.push({kn, right, bottom});
        }
    }
    return cnt;  // 回傳數量
}

int main() {
    int k, x, y;
    while(scanf("%d %d %d", &k, &x, &y) != EOF) {
        if (k == 0 && x == 0 && y == 0) continue;
        printf("%3d\n", count_squares(k, x, y));
    }
    return 0;
}