UVa 232 Crossword Answers（填字遊戲編號）問題詳解與實現

編輯：關於C語言

UVa 232 Crossword Answers（填字遊戲編號）問題詳解與實現

給定r×c（r,c≤10）填字遊戲網格，*為黑格，字母為白格。按規則為白格編號：白格若左邊或上邊是黑格/邊界，則為橫向/縱向起始格，獲得編號。編號從1開始，掃描順序：第1行全行，第2行符合條件者，以此類推。輸出所有橫向詞（按編號遞增）與縱向詞。

編號規則形式化

對位置(i,j)（0-based），若grid[i][j] != '*'且滿足：

i==0 || grid[i-1][j]=='*' → 縱向起始格
j==0 || grid[i][j-1]=='*' → 橫向起始格

若任一條件滿足，分配下一個編號num++，記錄(i,j,num)到橫向/縱向列表。

提取單詞

橫向：從(i,j)向右讀取，直到j==c-1或grid[i][j+1]=='*'。
縱向：從(i,j)向下讀取，直到i==r-1或grid[i+1][j]=='*'。

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

#include 
#include 
#include 

struct Item { int x, y, num; } across[400], down[400];
char grid[20][20];
int mark[20][20]; // 編號標記
int r, c, acCnt, downCnt, num, caseNo;

int main() {
    caseNo = 1;
    while (scanf("%d", &r) == 1 && r) {
        scanf("%d", &c);
        for (int i = 0; i < r; ++i) scanf("%s", grid[i]);
        memset(mark, 0, sizeof(mark));
        acCnt = downCnt = num = 0;
        // 掃描編號
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                if (isalpha(grid[i][j])) {
                    if (i==0 || grid[i-1][j]=='*') mark[i][j] = 1;
                    if (j==0 || grid[i][j-1]=='*') mark[i][j] = 1;
                }
        // 分配編號並分類
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < c; ++j)
                if (mark[i][j]) {
                    mark[i][j] = ++num;
                    if (i==0 || grid[i-1][j]=='*')
                        down[downCnt++] = {i, j, num};
                    if (j==0 || grid[i][j-1]=='*')
                        across[acCnt++] = {i, j, num};
                }
        // 輸出
        if (caseNo > 1) printf("\n");
        printf("puzzle #%d:\n", caseNo++);
        printf("Across\n");
        for (int i = 0; i < acCnt; ++i) {
            printf("%3d.", across[i].num);
            for (int j = 0;; ++j) {
                putchar(grid[across[i].x][across[i].y + j]);
                if (across[i].y + j == c-1 || grid[across[i].x][across[i].y + j + 1] == '*') break;
            }
            putchar('\n');
        }
        printf("Down\n");
        for (int i = 0; i < downCnt; ++i) {
            printf("%3d.", down[i].num);
            for (int j = 0;; ++j) {
                putchar(grid[down[i].x + j][down[i].y]);
                if (down[i].x + j == r-1 || grid[down[i].x + j + 1][down[i].y] == '*') break;
            }
            putchar('\n');
        }
    }
    return 0;
}