2013年7月30日 星期二

11664 - Langton's Ant

數學家 Christopher Langton 設計一套簡單的細胞自動機,名為 Langton's ant,根據給定的一個簡單行為規則但卻有趣的行為,這個行為是數學家研究的課題。


從分析螞蟻行為以及 Langton 的細胞自動機,根據給定的當下自動機的狀態,以及全自動的螞蟻能力,將會發現螞蟻呈現一個特別的走訪模式,進行探索這個世界。

螞蟻的世界為一個 n x n 的平面,每一格塗上藍色或者是紅色,而每一格座標定義 (i, j) (1 <= i, j <= n),螞蟻的移動規則如下:

  • 如果當前在藍色格子,她會將格子變成紅色,並且向左轉 90 度,並且朝這個方向前進一格。
  • 如果當前在藍色格子,她會將格子變成紅色,並且向右轉 90 度,並且朝這個方向前進一格。
  • 如果移動失敗,即掉出格子外,螞蟻則宣告死亡。
例如:假設有一隻螞蟻現在在紅色格子上,並且面朝東方,而牠會將這格變成紅色,並且面朝南方,如果南方沒有格子可走,那麼牠則會死亡 。反之,則會走下南方的那一格,並且重複步驟進行移動。


根據給定的狀態以及當前螞蟻所在位置,你的任務是要決定螞蟻能不能到達 (n, n)

假設螞蟻一開始面朝北方

Input 

由於狀態是 n x n ,可以表示 n2 bits 的二進制數字,方便起見定義 0 是藍色,1 是紅色。而給定的順序為由左而右、由下而上。

例如:0100 (十進制為 4) 表示一個 2 x 2 的狀態

blue blue
blue red

而  011010100 (十進制為 212) 表示一個 3 x 3 的狀態

red blue blue
blue red blue
blue red red

額外補充:相對應座標如下 (x, y)
(3,1) (3,2)(3,3)
(2,1) (2,2)(2,3)
(1,1)(1,2)(1,3)

輸入有多組測資,每組測資第一行會有四個整數 n, c, x, y
  • n ( 1 <=  n  <= 16):狀態的大小
  • c ( 0 <= c  < 2(n2)):一個十進制表示  n2-bit 二進制數,其數值為上描述。
  • (x, y):表示螞蟻一開始所在的位置 (1 <= x, y <= n)。
n = c = x = y = 0 結束程式。

Output 

對於每組測資,輸出格式為以下兩種的其中一種:

  • `Yes':如果螞蟻能夠抵達 (n, n)
  • `Kaputt!':如果螞蟻無法抵達 (n, n)
對於每組測資,保證一定會在有限步數內得到其中一種結果。

Sample Input 

2 8 1 1
2 4 1 1
2 15 1 1
0 0 0 0

Sample Output 

Yes
Kaputt!
Kaputt!