ZeroJudge 解題筆記：m802. 填字遊戲 (Puzzle)

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



ZeroJudge 題目連結：m802. 填字遊戲 (Puzzle)

解題想法

這題只有向下、向右填入字元兩種解法，依照測資檢查是否能填入指定的單字即可。注意，這題給的格子座標 (x, y) 是 (c, r)，跟二維陣列的索引值順序相反。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 格子維度
    grid = [['0']*n for _ in range(n)]  # 格子 n*n，先填入字元 0
    m = int(input())  # 填入 m 個單字
    solve = True  # 是否有解
    for _ in range(m):  # 執行 m 次
        d, s, c, r = input().split()  # 方向 d，字串 s，座標 (r, c)
        r, c = int(r), int(c)
        if d == 'V':  # 向下填
            if grid[r][c] != '0' and grid[r][c] != s[0]:  # 先檢查開頭，如果已填入字元而且不等於 s[0]
                solve = False  # 無解
            else: grid[r][c] = s[0]  # 填入 s[0]
            for j in range(1, len(s)):  # 往下填入剩下的字元
                nr = r+j  # 新的列
                if nr >= n or (grid[nr][c] != '0' and grid[nr][c] != s[j]):  # 如果出界或已填入字元而且不等於 s[j]
                    solve = False; break  # 無解，中止迴圈
                else: grid[nr][c] = s[j]  # 填入 s[j]
        elif d == 'H':  # 向右填
            if grid[r][c] != '0' and grid[r][c] != s[0]:  # 先檢查開頭，如果已填入字元而且不等於 s[0]
                solve = False  # 無解
            else: grid[r][c] = s[0]  # 填入 s[0]
            for j in range(1, len(s)):  # 往右填入剩下的字元
                nc = c+j  # 新的欄
                if nc >= n or (grid[r][nc] != '0' and grid[r][nc] != s[j]):  # 如果出界或已填入字元而且不等於 s[j]
                    solve = False; break  # 無解
                else: grid[r][nc] = s[j]  # 填入 s[j]
    print("Yes" if solve else "No")  # 印出答案

C++ 程式碼

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

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 格子維度
    while(cin >> n) {
        char grid[n][n];  // 格子 n*n
        for(int r=0; r<n; r++) {  // 先填入字元 0
            for(int c=0; c<n; c++) grid[r][c] = '0';
        }
        int m; cin >> m;  // 填入 m 個單字
        bool solve = true;  // 是否有解
        for(int i=0; i<m; i++) {  // 執行 m 次
            char d; int r, c; string s;  // 方向 d，座標 (r, c)，字串 s
            cin >> d >> s >> c >> r;
            if (d == 'V') {  // 向下填
                if (grid[r][c] != '0' && grid[r][c] != s[0]) {  // 先檢查開頭，如果出界或已填入字元而且不等於 s[0]
                    solve = false;  // 無解
                } else {
                    grid[r][c] = s[0];  // 填入 s[0]
                }
                for(int j=1; j<(int)s.size(); j++) {  // 往下填入剩下的字元
                    int nr = r+j;  // 新的列
                    if (nr >= n || (grid[nr][c] != '0' && grid[nr][c] != s[j])) {  // 如果已填入字元而且不等於 s[j]
                        solve = false; break;  // 無解，中止迴圈
                    } else {
                        grid[nr][c] = s[j];  // 填入 s[j]
                    }
                }
            } else if (d == 'H') {  // 向右填
                if (grid[r][c] != '0' && grid[r][c] != s[0]) {  // 先檢查開頭，如果已填入字元而且不等於 s[0]
                    solve = false;  // 無解
                } else {
                    grid[r][c] = s[0];  // 填入 s[0]
                }
                for(int j=1; j<(int)s.size(); j++) {  // 往右填入剩下的字元
                    int nc = c+j;  // 新的欄
                    if (nc >= n || (grid[r][nc] != '0' && grid[r][nc] != s[j])) {  // 如果出界或已填入字元而且不等於 s[j]
                        solve = false; break;  // 無解
                    } else {
                        grid[r][nc] = s[j];  // 填入 s[j]
                    }
                }
            }
        }
        cout << (solve ? "Yes\n" : "No\n");  // 印出答案
    }
    return 0;
}