藍橋杯歷屆真題：蘭頓螞蟻模擬解法詳解

題目背景與規則

蘭頓螞蟻是一種經典的細胞自動機模型，由克里斯·蘭頓於1986年提出。在一個由黑白格子組成的平面上，一隻螞蟻按照簡單規則移動：

• 若螞蟻位於黑格：右轉90度，將該格翻轉為白格，並向前移動一格
• 若螞蟻位於白格：左轉90度，將該格翻轉為黑格，並向前移動一格

儘管規則極其簡單，螞蟻的軌跡卻呈現出驚人的複雜性：初期近似對稱，經過漫長混沌後會形成規則的「高速公路」結構。

問題描述

給定一個 m×n 的方格棋盤（3 < m,n < 100），每個格子初始狀態為白(0)或黑(1)。螞蟻從坐標(x,y)出發，朝向為U/D/L/R（上下左右），模擬其走 k 步後的最終位置。

核心解題思路

直接模擬即可，關鍵在於：

1. 維護螞蟻的當前位置與朝向
2. 根據當前格顏色決定轉向、翻色、前進
3. 注意邊界條件：題目保證螞蟻不會走出邊界

方向處理技巧

將四個方向編碼為 0:上, 1:右, 2:下, 3:左，對應增量數組：

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

右轉：dir = (dir + 1) % 4；左轉：dir = (dir + 3) % 4。

完整代碼實現

#include <iostream>
#include <cstdio>
using namespace std;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int grid[110][110];

int main() {
    int m, n;
    while (~scanf("%d%d", &m, &n)) {
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                scanf("%d", &grid[i][j]);
        
        int x, y, k;
        char dirChar;
        scanf("%d %d %c %d", &x, &y, &dirChar, &k);
        
        int dir;
        if (dirChar == 'U') dir = 0;
        else if (dirChar == 'R') dir = 1;
        else if (dirChar == 'D') dir = 2;
        else dir = 3;
        
        for (int step = 0; step < k; ++step) {
            if (grid[x][y] == 1) { // 黑格
                dir = (dir + 1) % 4; // 右轉
                grid[x][y] = 0;      // 翻為白
            } else {                 // 白格
                dir = (dir + 3) % 4; // 左轉
                grid[x][y] = 1;      // 翻為黑
            }
            x += dx[dir];
            y += dy[dir];
        }
        printf("%d %d\n", x, y);
    }
    return 0;
}

樣例測試

輸入：

5 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
2 3 L 5

輸出： 1 3

複雜度分析

時間複雜度 O(k)，空間複雜度 O(m×n)，完全滿足 1 秒、256 MB 的限制。