Description

超級貓貓 Poo 是一隻充滿冒險精神的貓咪,這次牠受邀成為「喵喵地理學會」的特別研究員!🐱✨

這份工作要求 Poo 研究一張神秘的大陸地圖,這張地圖由不同的國家組成,每個國家都用一個數字來表示,而 Poo 的工作是要回答每個國家各自和哪些國家接壤。

但這張神秘的地圖好大一張啊啊啊啊啊 ! Poo 需要你的幫助,請寫一個程式,分析這張地圖,並找出每個國家分別與哪些國家接壤!

Input Format

第一行給定兩個數字 $N$、$M$,表示給定的是 $N \times M$ 的地圖(二維陣列)
( $N$ 列 rows,$M$ 行 columns)

接下來有 $N$ 行輸入,每行有 $M$ 個數字,表示這張地圖的資料,其中:
1. 第 $i$ 行第 $j$ 個數字,若非 $0$,則表示地圖上 $(i,j)$ 格屬於哪個國家。
2. 若數字為 $0$ 則代表海洋,不屬於任何國家。(不需視為接壤國家)
3. 相鄰的格子(上下左右四個方向相連)視為接壤的國家,請找出每個國家分別和哪些國家接壤。

若總國家數為 $K$ 則保證國家編號必定是 $1$ 到 $K$。
不影響最終答案,但存在有飛地、島嶼的可能性。

$1\leq N,M \leq 30$、$0\leq K \leq 32$。

Output Format

第一行請輸出總共有幾個國家。
假設國家數為 $K$,接下來 $K$ 行,請依照國家編號順序,輸出該國家和哪些國家接壤。
接壤的國家也請照國家編號順序排列。
若該國存在,但不和任何國家接壤,也請直接輸出一行,但不含任何內容。

輸出格式如下舉例:

  1. 國家 $1$ 和 國家 $2$, $3$ 接壤
  2. 國家 $2$ 和 國家 $1$, $3$ 接壤
  3. 國家 $3$ 和 國家 $1$, $2$ 接壤
  4. 國家 $4$ 存在,但不和任何國家接壤

一共四個國家

請輸出:

4
1: 2 3 
2: 1 3 
3: 1 2 
4: 

Sample Input 1

3 3
3 1 2
3 3 3
3 1 2

Sample Output 1

3
1: 2 3
2: 1 3
3: 1 2

Sample Input 2

6 17
0 4 4 4 4 4 4 4 4 4 4 4 4 4 4 0 7
0 4 3 3 3 3 1 4 1 1 1 4 4 4 4 0 0
0 4 3 3 3 1 1 1 1 1 1 1 4 4 4 0 0
5 5 5 5 5 5 5 5 6 5 5 5 5 5 5 5 0
0 4 3 3 2 2 2 2 2 2 2 2 2 2 4 0 0
0 4 4 4 4 4 4 4 4 4 4 4 4 4 4 0 0

Sample Output 2

7
1: 3 4 5 6
2: 3 4 5 6
3: 1 2 4 5
4: 1 2 3 5
5: 1 2 3 4 6
6: 1 2 5
7:

Sample Input 3

1 1
0

Sample Output 3

0

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~10 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1