codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
import core.stdc.stdio: printf, scanf; import std.math: abs; import std.algorithm: max, min; import std.numeric: gcd; // gcd is not nothrow void main() /*nothrow*/ { int tc; scanf("%d", &tc); foreach (tci; 0 .. tc) { int h, w, d; scanf("%d%d%d", &h, &w, &d); int sY = -1, sX = -1; char[40][40] tbl = void; foreach (y; 0 .. h) { scanf(" %s", tbl[y].ptr); foreach (x; 0 .. w) { if (tbl[y][x] == 'X') { sY = y; sX = x; } } } bool[101][101] vis = void; foreach (y; -d .. d + 1) foreach (x; -d .. d + 1) vis[y + d][x + d] = false; int cnt = 0; foreach (tY; -d .. d + 1) { foreach (tX; -d .. d + 1) { if (tY ^^ 2 + tX ^^ 2 > d ^^ 2) continue; if (tY == 0 && tX == 0) continue; immutable int yDen = max(1, abs(tX)) * 2; immutable int xDen = max(1, abs(tY)) * 2; int pY = tY > 0 ? 1 : (tY < 0 ? -1 : 0); int pX = tX > 0 ? 1 : (tX < 0 ? -1 : 0); int cy = (sY * 2 + 1) * yDen / 2; int cx = (sX * 2 + 1) * xDen / 2; int rest = max(abs(tY) * yDen, abs(tX) * xDen); while (true) { debug printf("t=(%d, %d), p=(%d/%d, %d/%d), c=(%d/%d, %d/%d), rest=%d\n", tY, tX, pY, yDen, pX, xDen, cy, yDen, cx, xDen, rest); int horiz = (pY > 0) ? ((yDen - cy % yDen) % yDen) : ((pY < 0) ? cy % yDen : rest + 1); int vert = (pX > 0) ? ((xDen - cx % xDen) % xDen) : ((pX < 0) ? cx % xDen : rest + 1); if (horiz == 0 && vert == 0) { immutable int yy = pY > 0 ? (cy / yDen) : (cy / yDen - 1); immutable int yyR = pY > 0 ? (cy / yDen - 1) : (cy / yDen); immutable int xx = pX > 0 ? (cx / xDen) : (cx / xDen - 1); immutable int xxR = pX > 0 ? (cx / xDen - 1) : (cx / xDen); if (tbl[yy][xx] != '#') { horiz = yDen; vert = xDen; } else if (tbl[yy][xxR] == '#') { if (tbl[yyR][xx] == '#') { pY = -pY; pX = -pX; continue; } else { pY = -pY; continue; } } else { if (tbl[yyR][xx] == '#') { pX = -pX; continue; } else { debug printf("fail.\n"); break; } } } if (horiz == 0) { immutable int yy = pY > 0 ? (cy / yDen) : (cy / yDen - 1); immutable int xx = cx / xDen; if (tbl[yy][xx] == '#') { pY = -pY; continue; } else horiz = yDen; } if (vert == 0) { immutable int yy = cy / yDen; immutable int xx = pX > 0 ? (cx / xDen) : (cx / xDen - 1); if (tbl[yy][xx] == '#') { pX = -pX; continue; } else vert = xDen; } if (rest == 0) { if (cy == yDen * (sY * 2 + 1) / 2 && cx == xDen * (sX * 2 + 1) / 2) { // succeed immutable int ry = tY / gcd(abs(tX), abs(tY)); immutable int rx = tX / gcd(abs(tX), abs(tY)); debug printf("success.\n"); if (!vis[ry + d][rx + d]) { debug printf("added.\n"); cnt++; } vis[ry + d][rx + d] = true; break; } else { debug printf("fail.\n"); break; } } immutable int aug = min(rest, horiz, vert); rest -= aug; cy += pY * aug; cx += pX * aug; } } } printf("Case #%d: %d\n", tci + 1, cnt); } }
Private
[
?
]
Run code
Submit