ZeroJudge 解題筆記：n910. 數織 (Nonogram)

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


ZeroJudge 題目連結：n910. 數織 (Nonogram)

解題想法

先處理每欄的提示，依序讀取此欄每列的資料，計算此欄有幾個連續的 1，如果沒有任何 1 則填入 0。再處理每列的提示，依序讀取此列每欄的資料，計算此列有幾個連續的 1，如果沒有任何 1 則填入 0。

Python 程式碼

使用時間約為 1.6 s，記憶體約為 13 MB，通過測試。

import sys

for line in sys.stdin:
    N = int(line)  # 圖形 N*N
    grid = [list(map(int, input().split())) for _ in range(N)]  # 讀取地圖
    for c in range(N):  # 依序讀取每欄資料
        col = []  # 每欄提示
        cnt = 0  # 連續的 1 數量
        for r in range(N):  # 依序讀取每列資料
            if cnt != 0:  # 如果 cnt 不等於 0
                if grid[r][c] == 1: cnt += 1  # 如果 grid[r][c] 等於 1，cnt 加 1
                else:  # 如果 grid[r][c] 等於 0
                    col.append(cnt)  # 結算 cnt，將 cnt 加到 col
                    cnt = 0  # cnt 歸零
            elif grid[r][c] == 1: cnt = 1  # 如果 cnt 等於 0 而且 grid[r][c] 等於 1，cnt 設定為 1
        if cnt != 0: col.append(cnt)  # 如果 cnt 不等於 0，要再結算一次 cnt
        if col: print(*col)  # 如果 col 有資料，拆開後印出
        else: print(0)  # 如果 col 沒有資料，印出 0
    for r in range(N):  # 依序讀取每列資料
        row = []  # 每列提示
        cnt = 0  # 連續的 1 數量
        for c in range(N):  # 依序讀取每欄資料
            if cnt != 0:  # 如果 cnt 不等於 0
                if grid[r][c] == 1: cnt += 1  # 如果 grid[r][c] 等於 1，cnt 加 1
                else::  # 如果 grid[r][c] 等於 0
                    row.append(cnt)  # 結算 cnt，將 cnt 加到 col
                    cnt = 0  # cnt 歸零
            elif grid[r][c] == 1: cnt = 1  # 如果 cnt 等於 0 而且 grid[r][c] 等於 1，cnt 設定為 1
        if cnt != 0: row.append(cnt)  # 如果 cnt 不等於 0，要再結算一次 cnt
        if row: print(*row)  # 如果 row 有資料，拆開後印出
        else: print(0)  # 如果 row 沒有資料，印出 0

C++ 程式碼

使用時間約為 0.3 s，記憶體約為 4.1 MB，通過測試。

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

int main() {
    int N;  // 圖形 N*N
    while(scanf("%d", &N) != EOF) {
        int grid[N][N];  // 讀取地圖
        for(int r=0; r<N; r++) {
            for(int c=0; c<N; c++) scanf("%d", &grid[r][c]);
        }
        for(int c=0; c<N; c++) {  // 依序讀取每欄資料
            vector<int> col;  // 每欄提示
            int cnt = 0;  // 連續的 1 數量
            for(int r=0; r<N; r++) {  // 依序讀取每列資料
                if (cnt != 0) {  // 如果 cnt 不等於 0
                    if (grid[r][c] == 1) {  // 如果 grid[r][c] 等於 1，cnt 加 1
                        cnt++;
                    } else {  // 如果 grid[r][c] 等於 0
                        col.push_back(cnt);  // 結算 cnt，將 cnt 加到 col
                        cnt = 0;  // cnt 歸零
                    }
                } else if (grid[r][c] == 1) {  // 如果 cnt 等於 0 而且 grid[r][c] 等於 1，cnt 設定為 1
                    cnt = 1;
                }
            }
            if (cnt != 0) col.push_back(cnt);  // 如果 cnt 不等於 0，要再結算一次 cnt
            if (!col.empty()) {  // 如果 col 有資料，拆開後印出
                for(int i = 0; i<(int)col.size(); i++) {
                    printf("%d", col[i]);
                    if (i == (int)col.size()-1) printf("\n");
                    else printf(" ");
                }
            } else {  // 如果 col 沒有資料，印出 0
                printf("0\n");
            }
        }
        for(int r=0; r<N; r++) {  // 依序讀取每列資料
            vector<int> row;  // 每列提示
            int cnt = 0;  // 連續的 1 數量
            for(int c=0; c<N; c++) {  // 依序讀取每列欄資料
                if (cnt != 0) {  // 如果 cnt 不等於 0
                    if (grid[r][c] == 1) {  // 如果 grid[r][c] 等於 1，cnt 加 1
                        cnt++;
                    } else {  // 如果 grid[r][c] 等於 0
                        row.push_back(cnt);  // 結算 cnt，將 cnt 加到 row
                        cnt = 0;  // cnt 歸零
                    }
                } else if (grid[r][c] == 1) {  // 如果 cnt 等於 0 而且 grid[r][c] 等於 1，cnt 設定為 1
                    cnt = 1;
                }
            }
            if (cnt != 0) row.push_back(cnt);  // 如果 cnt 不等於 0，要再結算一次 cnt
            if (!row.empty()) {  // 如果 row 有資料，拆開後印出
                for(int i = 0; i<(int)row.size(); i++) {
                    printf("%d", row[i]);
                    if (i == (int)row.size()-1) printf("\n");
                    else printf(" ");
                }
            } else {  // 如果 rwo 沒有資料，印出 0
                printf("0\n");
            }
        }
    }
    return 0;
}