🥇 Taiwan

TOI 臺灣國際資訊奧林匹亞競賽 Taiwan Olympiad in Informatics 📅 2024/06/17~2024/06/21 🧒 新手組 T1

數織 (Nonogram)

---

📝 問題敘述

Nonogram 又稱數織，是一種圖形邏輯謎題，玩家需要根據數字提示填滿或空出格子，以形成一幅圖像。數字提示標示在行和列的外側，指示連續的塊狀格子的數量和順序。

圖一為一個正確填寫完畢的數織，第一直行為 5 表示該行需連續填滿五格。第二橫列為 3 1，表示有三個連續填滿的格和一個單獨的填色格子。

圖二的數字提示錯誤，按照此填色方式，第二列的 3 1 應為 4，第四行應為 1 1，第五行應為 1 3。

圖一：正確數織

圖二：錯誤的數織數字提示

現在你需要設計一個程序，根據輸入的填色格子，輸出每個行列相應的數字提示。

---

📥 輸入格式

• 第一列輸入一個正整數 N（1 ≤ N ≤ 1000），表示 N × N 的數織。
• 接下來輸入 N 列，每行有 N 個數字（0 或 1），以空白間隔，0 代表空白格子，1 代表填色格子。

---

📤 輸出格式

• 輸出 2 × N 列：
  • 前 N 列依序表示每行的數字提示，同一行的數字提示以空白間隔；
  • 後 N 列依序表示每列的數字提示，同一列的數字提示以空白間隔；
• 如果該行列沒有任何填色格子，則輸出 0。

---

📚 範例 1

輸入：

5
1 0 0 0 1
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 0 1 1

輸出：

5
1
3
1
5
1 1
3 1
1 1 1
1 1 1
1 2

---

📚 範例 2

輸入：

5
1 0 0 0 1
1 1 1 1 0
1 0 1 0 1
1 0 1 0 1
1 0 0 1 1

輸出：

5
1
3
1 1
1 3
1 1
4
1 1 1
1 1 1
1 2

---

📚 範例 3

輸入：

5
0 0 0 0 0
0 1 1 1 0
0 0 1 0 0
0 0 1 0 0
0 0 0 1 1

輸出：

0
1
3
1 1
1
0
3
1
1
2

---

💡 評分說明

此題目測資分為兩組，每組測資有多筆測試資料，需答對該組所有測資才能獲得該組分數。各組詳細限制如下：

1. ​**第一組（40 分）**​：每行與每列都只會有一段連續格子。
2. ​**第二組（60 分）**​：無特殊限制。

---

💡 思路說明

1. ​行和列的數字提示​：
   • 對於每行，計算該行中連續的 1 的區段數，並記錄每個區段的長度。
   • 對於每列，計算該列中連續的 1 的區段數，並記錄每個區段的長度。
2. ​處理無填色格子的情況​：
   • 如果該行或該列沒有任何 1，則輸出 0。
3. ​輸出格式​：
   • 行數字提示和列數字提示需要按照指定格式輸出。

---

🎯 解題策略

1. ​遍歷每行​：對每一行，計算該行中的連續 1 區段並記錄長度。
2. ​遍歷每列​：對每一列，計算該列中的連續 1 區段並記錄長度。
3. ​輸出結果​：根據計算結果，依序輸出行和列的數字提示。

---