UVA 10620 - A Flea on a Chessboard
题意：给定一个跳蚤位置和移动方向。如今在一个国际象棋棋盘上，左下角为黑格，一个格子为s*s，推断是否能移动到白格子。问要移动多少次才干到白格，边界不算白格。
思路：利用鸽笼原理落在黑格子和边界上的一共同拥有（s + 1)^2个点，也就是说。假设形成循环，周期肯定在这之内。所以能够不断去模拟跳格子，直到踩到白格，或者踩到之前落到过的黑格就结束
只是事实上还有更优的方法，由于跳蚤跳跃路径为直线，观察下能够发现假设能够到白格，最多连成一条小于(2 x 2)格子对角线长度的线，那么上面一共同拥有不超过2 * s个黑点，于是事实上仅仅须要推断前2s步能不能到白格就能够了，假设不能。说明必定中间形成了周期，也就是始终到不了白格了
代码：
原来的：
#include <stdio.h>
#include <string.h> const int N = 1005;
bool vis[N][N];
long long s, x, y, dx, dy; bool white() {
if (x % s == 0 || y % s == 0) return false;
if (((x / s)&1)^((y / s)&1)) return true;
return false;
} bool in() {
if (x > s || y > s) {
x -= s; y -= s;
if (x < 0) x = s;
if (y < 0) y = s;
}
if (vis[x][y]) return false;
vis[x][y] = true;
return true;
} int main() {
while (~scanf("%lld%lld%lld%lld%lld", &s, &x, &y, &dx, &dy) && s) {
memset(vis, false, sizeof(vis));
long long ans = 0, ansx = x, ansy = y;
while (1) {
x %= 2 * s;
y %= 2 * s;
if (white()) {
printf("After %lld jumps the flea lands at (%lld, %lld).\n", ans, ansx, ansy);
break;
}
if (!in()) {
printf("The flea cannot escape from black squares.\n");
break;
}
x += dx;
y += dy;
ansx += dx;
ansy += dy;
ans++;
}
}
return 0;
}
简化后的：
#include <stdio.h>
#include <string.h> long long s, x, y, dx, dy; bool judge(long long x, long long y) {
return (x % s && y % s && (x / s + y / s) % 2);
} int main() {
while (~scanf("%lld%lld%lld%lld%lld", &s, &x, &y, &dx, &dy) && s) {
int i;
for (i = 0; i < 2 * s; i++) {
if (judge(x, y)) {
printf("After %d jumps the flea lands at (%lld, %lld).\n",i,x,y);
break;
}
x += dx; y += dy;
}
if (i == 2 * s) printf("The flea cannot escape from black squares.\n");
}
return 0;
}