[ZJ] d618. 有限狀態自動機（Finite State Machine）

http://zerojudge.tw/ShowProblem?problemid=d618

內容 ：

有限狀態自動機（Finite State Machine）是由有限個狀態以及在這些狀態之間的轉移和動作等行為所組成的數學模型。
有限狀態自動機可以使用狀態轉移圖（State Transition Diagram）來表示，例如下面的狀態轉移圖，表示的是一個可以用來判斷二進位數是否具有偶數個 0 的有限狀態自動機。「沒有起點的箭頭」指向狀態 S₁，表示狀態 S₁ 是開始狀態（Start State）；狀態 S₁ 為雙重圓圈，表示狀態 S₁ 是接受狀態（Accept State）。
輸入二進位數，例如 10101，一開始的狀態是狀態 S₁；讀到第一個 1 的時候，依然停留在狀態 S₁；讀到第一個 0 的時候，移動到狀態 S₂；讀到第二個 1 的時候，依然停留在狀態 S₂；讀到第二個 0 的時候，移動到狀態 S₁；讀到第三個 1 的時候，依然停留在狀態 S₁；因為狀態 S₁ 是接受狀態，表示輸入的二進位數 10101 具有偶數個 0。

如果輸入的二進位數是 10010，最後會停留在狀態 S₂。因為狀態 S₂ 不是接受狀態，所以我們可以知道二進位數 10010 不具有偶數個 0。

有限狀態自動機也可以使用狀態轉移表（State Transition Table）來表示，例如上面(上一頁)的狀態轉移圖可以表示為：


現在假設葆葆班長定義了以下狀態

1. 立正 ( 起立 )
2. 稍息
3. 蹲下
4. 坐下
5. 向右轉
6. 向左轉
7. 向後轉

 另外

• 狀態 2 時只能改變狀態為 1
• 狀態 3. 4 可以互換或改變為狀態 1

輸入說明 ：

第一行為一整數 T ( T ≤ 20 )
代表下面有 T 組測試資料
每組測試資料一行字串 ( 由 1 ~ 7 組成，字元長度不超過 100 )
代表一連串的狀態 ( 假設起始狀態為 1 )

輸出說明 ：

輸出最後的狀態 ( 一個數字 )

範例輸入 ：

31234162146121212121

範例輸出 ：

241

提示 ：

 ¤ 相關題目內容取自 2009 NPSC 國中組決賽

出處 ：

葆葆 (管理：maxyuan)

/**********************************************************************************/
/*  Problem: d618 "有限狀態自動機（Finite State Machine）" from 葆葆   */
/*  Language: C                                                                   */
/*  Result: AC (4ms, 270KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-05-30 21:32:58                                     */
/**********************************************************************************/


#include<stdio.h>
main() {
    int T, a;
    int Map[8][8] = {{0,0,0,0,0,0,0,0},
                     {1,1,1,1,1,1,1,1},
                     {0,1,1,0,0,0,0,0},
                     {0,1,0,1,1,0,0,0},
                     {0,1,0,1,1,0,0,0},
                     {0,1,1,1,1,1,1,1},
                     {0,1,1,1,1,1,1,1},
                     {0,1,1,1,1,1,1,1}
                    };
    char S[101];
    scanf("%d", &T);
    while(T--) {
        scanf("%s", S);
        int now = S[0] - '0';
        for(a = 1; S[a]; a++) {
            if(Map[now][S[a] - '0'])
                now = S[a] - '0';
        }
        printf("%d\n", now);
    }
    return 0;
}