Langton's Ant

Langton's ant, after the mathematician Christopher Langton, is a cellular automaton with a very simple set of rules but interesting emergent behavior; this behavior is currently the matter of research for some mathematicians. The analogy between ants and Langton's cellular automaton comes from the observation that one can arbitrarily identify the state of the automaton as the ``ant'', and the dynamics of the automaton with the ability of the ant to travel in a special world.

The ant world's is an n x n plane where the squares (or cells) on the plane are colored variously either blue or red. The number n is called the size of the world. A cell is denoted with a pair (i, j), (1i, jn). The ant lives and moves in single steps following the rules below:

• if it is on a blue cell, it flips the color of the cell, turns to the left, and moves forward to the next cell in the direction it is facing;
• if it is on a red cell, it flips the color of the cell, turns to the right, and moves forward to the next cell in the direction it is facing; and
• if a movement is impossible (because the ant cannot move out of the world), then the ant dies.

For example, let us assume the ant is in a red cell while facing east. If there is not a cell immediately to its south, then the ant dies. On the contrary, if there is a cell immediately to its south, then the ant takes a single step by moving to this cell to which it arrives facing south and the color of its source cell flips to blue. Then, the ant will try to take another single step, and so on.

Your task is to determine if the ant can go to the (n, n) cell of a world, given (i) the configuration of the world, and (ii) the initial position of the ant. You are to assume the ant's initial direction is north.

Input 

The configuration of an n x n world can be codified as a natural number in binary notation by using n² bits. We adopt the following conventions: 0 = blue, 1 = red, and the binary representation of the configuration identifies the cells of the world from left to right and from bottom to top (considering the bits from the most significant bit to the least significant bit). For example, the binary number 0100 (4 in decimal notation) represents a 2 x 2 world with the following configuration:

Coherently, the binary number 011010100 (212 in decimal notation) represents a 3 x 3 world with the following configuration:

The problem input has several test cases. Each case consists of a single line containing a list of four natural numbers, n, c, x, y, separated by blanks, that should be interpreted as:

• n (1 n 16): the size of the world;
• c (0 c < 2⁽ⁿ²⁾): decimal representation of an n²-bit binary number that describes an initial configuration of the world, as above explained;
• (x, y): coordinates of the initial position of the ant in the world (1 x, y n), where the position (n, n) corresponds to the least significant bit of c.

The end of the input is indicated by a line where n = c = x = y = 0.

Output 

For each test case your solution should output:

• `Yes' if the ant reaches the cell (n, n) from the initial position;
• `Kaputt!' if the ant dies without reaching the cell (n, n) from the initial position.

For each test case, it's guaranteed that after a finite number of steps, the ant reaches the cell (n, n) or dies without reaching the cell (n, n).

Sample Input 

2 8 1 12 4 1 12 15 1 10 0 0 0

Sample Output 

YesKaputt!Kaputt!

---

題目描述：

給定一個盤面，螞蟻根據當前位置的顏色進行操作，先順時針或者逆時針轉一個方向，先將這個顏色反轉，然後走一步出去。問能不能抵達 (n, n)。

題目解法：

這題其實不難，主要是模擬，但是處理要大數轉成二進制數，困難點在於沒有給定座標


      x = 1,x = 2,x= 3

y = 3  red	blue	blue
y = 2 blue	red	blue
y = 1 blue	red	red

而一開始給定的座標是 (y, x)，面對北方。北方是正上方，東方是右手邊。

#include <stdio.h>
#include <string.h>
char bin[105];
int g[20][20], bb[105], len;
int getBit() {
    int i, ret = 0;
    for(i = len; i >= 0; i--) {
        ret = ret*10 + bb[i];
        bb[i] = ret/2;
        ret %= 2;
    }
    while(len >= 0 && bb[len] == 0)
        len--;
    return ret;
}
int main() {
    int n, x, y;
    int i, j, k;
    int dx[] = {1,0,-1,0};//NESW
    int dy[] = {0,1,0,-1};
    while(scanf("%d %s %d %d", &n, bin, &y, &x) == 4 && n) {
        x--, y--;
        len = strlen(bin);
        memset(bb, 0, sizeof(bb));
        for(i = 0, j = len-1; i < len; i++, j--)
            bb[i] = bin[j]-'0';
        for(i = n-1; i >= 0; i--) {
            for(j = n-1; j >= 0; j--)
                g[i][j] = getBit();
        }
        int dir = 0;
        int step = 0, found = 0;
        while(step++ < 1000) {
            if(x < 0 || y < 0 || x >= n || y >= n)
                break;
            if(x == n-1 && y == n-1) {
                found = 1;
                break;
            }
            if(g[x][y] == 0) {//blue
                g[x][y] = !g[x][y];
                dir = (dir-1+4)%4;
                x += dx[dir], y += dy[dir];
            } else {//red
                g[x][y] = !g[x][y];
                dir = (dir+1)%4;
                x += dx[dir], y += dy[dir];
            }
        }
        //printf("%d %d\n", found, step);
        puts(found ? "Yes" : "Kaputt!");
    }
    return 0;
}