UVA 10620 A Flea on a Chessboard：跳蚤棋盤模擬 + 週期性剪枝

問題描述

無限棋盤，左下角 (0,0) 為黑格，格子長 s。跳蚤從 (x,y) 起跳，每步位移 (dx,dy)。判斷能否落在白格，能則輸出步數和座標，否則輸出不能逃離。

關鍵觀察：2s×2s 週期

黑白格以 2s 為周期重複。跳蚤位置 (x + k*dx, y + k*dy) 模 2s 後狀態最多 2s 步循環。只需模擬前 2s 步。

判斷白格條件

座標 (X,Y) 所在格行列：col = X/s, row = Y/s（整除）。顏色：(col+row)%2==0 為黑，==1 為白。邊界上（X%s==0 或 Y%s==0）視為線上不算落在格內，需繼續跳。

完整參考代碼

#include <cstdio>
bool isWhite(int x,int y,int s){
    if(x%s==0 || y%s==0) return false; // 在格線上
    return ((x/s + y/s) & 1) == 1;
}
int main(){
    int s,x,y,dx,dy;
    while(scanf("%d%d%d%d%d",&s,&x,&y,&dx,&dy)==5 && s+x+y+dx+dy){
        int ans=-1;
        for(int step=0; step<2*s; step++){
            if(isWhite(x,y,s)){
                ans=step; break;
            }
            x+=dx; y+=dy;
        }
        if(ans==-1) puts("The flea cannot escape from black squares.");
        else printf("After %d jumps the flea lands at (%d, %d).\n", ans, x-dx, y-dy);
    }
    return 0;
}

總結

UVA 10620 利用棋盤顏色週期性將無限模擬縮減為 2s 步有限枚舉，邊界判斷（格線不計入）是關鍵細節。