UVA 227 Puzzle（5×5滑塊拼圖）問題詳解與模擬實現

編輯：關於C語言

UVA 227 Puzzle（5×5滑塊拼圖）問題詳解與模擬實現

經典5×5滑塊拼圖：24個字母+1個空格。輸入初始佈局（5行，每行5字符，空格表示空位），然後輸入移動序列（A上、B下、L左、R右，表示哪塊字母移動到空格），以0結束。若出現非法移動（如邊界外），該拼圖無最終佈局。多組數據，Z結束輸入。輸出最終佈局（字符間單空格）或This puzzle has no final configuration.。

核心邏輯

讀取5行初始佈局，記錄空格位置(sx,sy)。
循環讀取命令行，逐字符處理：
- A：空格上方字母下移 → sx>0？交換grid[sx][sy]與grid[sx-1][sy]，sx--：否則非法。
- B：空格下方字母上移 → sx<4？交換sx+1，sx++：否則非法。
- L：空格左方字母右移 → sy>0？交換sy-1，sy--：否則非法。
- R：空格右方字母左移 → sy<4？交換sy+1，sy++：否則非法。
- 0：結束該拼圖。
非法標記一旦置位，後續命令仍需讀取完畢（直到0），但不再執行交換。
輸出：合法則打印5×5網格，字符間單空格；非法打印提示語。

關鍵避坑點

命令跨行讀取：移動序列可能分多行，需循環gets/fgets讀取直到遇到0。
非法後仍需消費輸入：發現非法移動後，不能break跳出命令讀取循環，必須繼續讀取直到0，否則下一個拼圖的初始佈局會被誤讀為命令。
空格查找：初始佈局中唯一空格，掃描5行找到' '。
輸出格式：拼圖編號Puzzle #1:，用例間空行，字符間單空格（空格位置顯示為兩個連續空格分隔符中間的空位）。

C語言參考實現（AC代碼）

#include 
#include 

char grid[5][6];  // 5行，每行5字符+'\0'
char cmd[3000];
int main() {
    int puzzle = 0;
    while (fgets(grid[0], 6, stdin) && grid[0][0] != 'Z') {
        // 讀完整5行
        for (int i = 1; i < 5; ++i) fgets(grid[i], 6, stdin);
        // 找空格
        int sx, sy;
        for (int i = 0; i < 5; ++i)
            for (int j = 0; j < 5; ++j)
                if (grid[i][j] == ' ') { sx = i; sy = j; }

        int illegal = 0;
        // 讀取命令直到 '0'
        while (fgets(cmd, sizeof(cmd), stdin)) {
            for (int i = 0; cmd[i]; ++i) {
                if (illegal) continue; // 非法後只消費輸入
                char c = cmd[i];
                if (c == '0') break;
                int nx = sx, ny = sy;
                if (c == 'A') nx = sx - 1;
                else if (c == 'B') nx = sx + 1;
                else if (c == 'L') ny = sy - 1;
                else if (c == 'R') ny = sy + 1;
                else continue;
                if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) {
                    illegal = 1;
                } else {
                    char tmp = grid[sx][sy];
                    grid[sx][sy] = grid[nx][ny];
                    grid[nx][ny] = tmp;
                    sx = nx; sy = ny;
                }
            }
            if (strchr(cmd, '0')) break;
        }

        if (puzzle++) printf("\n");
        printf("Puzzle #%d:\n", puzzle);
        if (illegal) {
            printf("This puzzle has no final configuration.\n");
        } else {
            for (int i = 0; i < 5; ++i) {
                for (int j = 0; j < 5; ++j) {
                    if (j) printf(" ");
                    printf("%c", grid[i][j]);
                }
                printf("\n");
            }
        }
    }
    return 0;
}