ZeroJudge 解題筆記：f340. 4.俄羅斯方塊 (Tetris)

作者：王一哲
日期：2025年3月4日



ZeroJudge 題目連結：f340. 4.俄羅斯方塊 (Tetris)

解題想法

這題要先寫出各種指令對應的操作，還要檢查方塊是否在邊界使方塊無法旋轉，寫起來很容易出錯。

Python 程式碼

使用時間約為 24 ms，記憶體約為 5.1 MB，通過測試。

# 方向：0 朝右，1 朝下，2 朝左，3 朝上
def bottom(x, y, d):  # 檢查是否已觸底，輸入錨點座標 (x, y)，方向 d
    if d == 3: return y >= n-1  # 朝上，回傳 y 是否大於等於 n-1
    else: return y+1 >= n-1  # 其它方向，回傳 y+1 是否大於等於 n-1
    
def zero(x, y, d):  # 指令 0，方向 d，向下移一格
    return x, y+1, d

def one(x, y, d):  # 指令 1，輸入錨點座標 (x, y)，方向 d，向右、向下移一格
    # 如果「方向朝右、下、上且 x+1 小於 m-1」或是「方向朝左且 x 小於 m-1」，可以向右移一格
    if (d in (0, 1, 3) and x+1 < m-1) or (d == 2 and x < m-1): x += 1
    return x, y+1, d

def two(x, y, d):  # 指令 2，輸入錨點座標 (x, y)，方向 d，向左、向下移一格
    # 如果「方向朝下、左、上且 x-1 大於 0」或是「方向朝右且 x 大於 0」，可以向左移一格
    if (d in (1, 2, 3) and x-1 > 0) or (d == 0 and x > 0): x -= 1
    return x, y+1, d

def three(x, y, d):  # 指令 3，輸入錨點座標 (x, y)，方向 d，置底
    if d == 3: return x, n-1, d  # 朝上，錨點 y = n-1
    else: return x, n-2, d  # 其它方向，錨點 y = n-2

def four(x, y, d):  # 指令 4，輸入錨點座標 (x, y)，方向 d，右旋
    if d == 2 and x == m-1: d = 2  # 朝左且 x 等於 m-1，不能右旋
    elif d == 0 and x == 0: d = 0  # 朝右且 x 等於 0，不能右旋
    else: d = (d+1)%4  # 右旋
    if bottom(x, y, d): return x, y, d  # 如果已經觸底，回傳 x, y, d
    return x, y+1, d  # 否則回傳 x, y+1, d

### 初始化 ###
m, n = map(int, input().split())  # 畫面寬度 m、高度 n
s = int(input())  # 指令數量 s
arr = list(map(int, input().split()))  # 指令
if m%2 == 1: x = (m+1)//2 - 1  # 如果 m 是奇數
else: x = m//2 - 1  # 如果 m 是偶數
y = 0  # 初位置 y 座標
d = 1  # 方向朝下
### 依照指令改變方塊的位置及方向 ###
for a in arr:  # 依序由 arr 讀取指令 a
    if a == 0: x, y, d = zero(x, y, d)  # 指令 0
    elif a == 1: x, y, d = one(x, y, d)  # 指令 1
    elif a == 2: x, y, d = two(x, y, d)  # 指令 2
    elif a == 3: x, y, d = three(x, y, d); break  # 指令 3，執行完畢後中止迴圈
    else: x, y, d = four(x, y, d)  # 指令 4
    if bottom(x, y, d): break  # 如果已經觸底中止迴圈
### 畫出最後的地圖 ###
grid = [[0]*m for _ in range(n)]  # 地圖
if d == 0:  # 朝右
    grid[y-1][x] = grid[y][x] = grid[y+1][x] = grid[y][x+1] = 1
elif d == 1:  # 朝下
    grid[y][x-1] = grid[y][x] = grid[y][x+1] = grid[y+1][x] = 1
elif d == 2:  # 朝左
    grid[y-1][x] = grid[y][x] = grid[y+1][x] = grid[y][x-1] = 1
else:  # 朝上
    grid[y][x-1] = grid[y][x] = grid[y][x+1] = grid[y-1][x] = 1
for g in grid: print(*g, sep='')  # 印出地圖

C++ 程式碼

使用時間約為 3 ms，記憶體約為 392 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 方向：0 朝右，1 朝下，2 朝左，3 朝上
struct Block {  // 方塊錨點位置 (x, y)，方向 d
    int x, y, d;
};
int m, n;  // 畫面寬度 m、高度 n

bool bottom(Block b) {  // 檢查是否已觸底，輸入方塊物件
    if (b.d == 3) return b.y >= n-1;  // 朝上，回傳 y 是否大於等於 n-1
    else return b.y+1 >= n-1;  // 其它方向，回傳 y+1 是否大於等於 n-1
}

Block zero(Block b) {  // 指令 0，輸入方塊物件，向下移一格
    Block t; t.x = b.x; t.y = b.y + 1; t.d = b.d;
    return t;
}

Block one(Block b) {  // 指令 1，輸入方塊物件，向右、向下移一格
    // 如果「方向朝右、下、上且 x+1 小於 m-1」或是「方向朝左且 x 小於 m-1」，可以向右移一格
    Block t; t.x = b.x; t.y = b.y + 1; t.d = b.d;
    if (((b.d == 0 || b.d == 1 || b.d == 3) && b.x+1 < m-1) || (b.d == 2 && b.x < m-1)) t.x++;
    return t;
}

Block two(Block b) {  // 指令 2，輸入方塊物件，向左、向下移一格
    // 如果「方向朝下、左、上且 x-1 大於 0」或是「方向朝右且 x 大於 0」，可以向左移一格
    Block t; t.x = b.x; t.y = b.y + 1; t.d = b.d;
    if (((b.d == 1 || b.d == 2 || b.d == 3) && b.x-1 > 0) || (b.d == 0 && b.x > 0)) t.x--;
    return t;
}

Block three(Block b) {  // 指令 3，輸入方塊物件，置底
    Block t;
    if (b.d == 3) {  // 朝上，錨點 y = n-1
        t.x = b.x; t.y = n-1; t.d = b.d;
    } else {  // 其它方向，錨點 y = n-2
        t.x = b.x; t.y = n-2; t.d = b.d;
    }
    return t;
}

Block four(Block b) {  // 指令 4，輸入方塊物件，右旋
    Block t;
    if (b.d == 2 && b.x == m-1) t.d = 2;  // 朝左且 x 等於 m-1，不能右旋
    else if (b.d == 0 && b.x == 0) t.d = 0;  // 朝右且 x 等於 0，不能右旋
    else t.d = (b.d+1)%4;  // 右旋
    if (bottom(t)) {
        return t;  // 如果已經觸底，回傳 t
    } else {  // 否則回傳 y+1 之後的 t
        t.x = b.x; t.y = b.y + 1;
        return t;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    /* 初始化 */
    cin >> m >> n;  // 畫面寬度 m、高度 n
    int s; cin >> s;  // 指令數量 s
    vector<int> arr (s);  // 指令
    for(int i=0; i<s; i++) cin >> arr[i];
    int x, y = 0;  // 方塊的初位置 (x, 0)
    if (m%2 == 1) x = (m+1)/2 - 1;  // 如果 m 是奇數
    else x = m/2 - 1;  // 如果 m 是偶數
    /* 依照指令改變方塊的位置及方向 */
    Block b; b.x = x; b.y = y; b.d = 1;
    for(int a : arr) {  // 依序由 arr 讀取指令 a
        if (a == 0) b = zero(b);  // 指令 0
        else if (a == 1) b = one(b);  // 指令 1
        else if (a == 2) b = two(b);  // 指令 2
        else if (a == 3) { b = three(b); break; }  // 指令 3，執行完畢後中止迴圈
        else b = four(b);  // 指令 4
        if (bottom(b)) break;  // 如果已經觸底中止迴圈
    }
    /* 畫出最後的地圖 */
    vector<vector<int>> grid (n, vector<int> (m, 0));  // 地圖
    if (b.d == 0) grid[b.y-1][b.x] = grid[b.y][b.x] = grid[b.y+1][b.x] = grid[b.y][b.x+1] = 1; // 朝右
    else if (b.d == 1) grid[b.y][b.x-1] = grid[b.y][b.x] = grid[b.y][b.x+1] = grid[b.y+1][b.x] = 1;  // 朝下
    else if (b.d == 2) grid[b.y-1][b.x] = grid[b.y][b.x] = grid[b.y+1][b.x] = grid[b.y][b.x-1] = 1;  // 朝左   
    else grid[b.y][b.x-1] = grid[b.y][b.x] = grid[b.y][b.x+1] = grid[b.y-1][b.x] = 1;  // 朝上
    for(int i=0; i<n; i++) {  // 印出地圖
        for(int j=0; j<m; j++) cout << grid[i][j];
        cout << "\n";
    }
    
    return 0;
}