[ create a new paste ] login | about

Link: http://codepad.org/TZwGLGjV    [ raw code | fork ]

D, pasted on Apr 16:
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);
    }
}


Create a new paste based on this one


Comments: