回分類題庫
g012: F.P方陣
關鍵字: NPSC 2005 國中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 42 Times / 35 Users | Submit : 94 Times / 37 Users | Accepted rate : 95%
題目加入時間 : 2011-12-06 10:06

Content: 简体中文

對最近正在流行的數獨遊戲(sudoku)有印象嗎?台大某位P教授對此道頗有些興趣,但很快簡單的數獨遊戲不再能滿足P教授荼毒學生的興趣,於是P教授把目標放大,P教授決定移除數獨大小9×9的限制,當然也只好移去每一九宮格的限制,他將這樣的方陣,稱做P方陣,它的定義如下:

所謂的N階P方陣(N>1),是指一個N×N的方陣,其每一行列都由1~N的正整數所構成,且每一個整數恰只出現一次。比方來說,下面是一個三階和四階P方陣:

P教授使用他獨特的、非常大張的格點筆記寫下他那堪比3GHz處理器頭腦所隨機產生的一堆P方陣;不過因為P教授的個性隨意,他於是很隨意的把他所找出的P方陣寫在筆記本上的各個地方。

問題不在P教授,而發生在P教授不在家的時候。P教授的大兒子,他偶然間看到爸爸的筆記本上充斥著他所看不懂的數字排列,一時心血來潮,他把筆記本上所有空的格點都填上一個隨機的正整數。P教授回到家,他只看到一張紙上滿滿的是數字,如下圖所示是一張6×6的筆記本:

P教授用筆將其中所有包含的P方陣(階數是任意的)標出來。但是他很快理解到這是另一個荼毒學生的好機會,於是這個問題就交給了你。

Input:

輸入檔的第一列有一個正整數T (1 ≤ T ≤ 40),表接下來有T頁筆記紙等待處理。
每頁筆記本的第一列會有兩個正整數A, B,表示該頁筆記共有A×B個格點被填滿了正整數(1 ≤ A, B ≤ 100) 。接下來的A列每列包含B個正整數,任兩正整數之間用一個空白字元隔開,正整數的範圍都在1到100之間。
任兩頁筆記本間不會有任何無意義的空行出現。

Output:

對於每頁筆記,分別要輸出數行訊息。第一列請先輸出:

Page #T:

表示這是第T頁所處理的筆記,T從1開始數。接下來請依N的順序 (由2開始、從小到大),輸出該頁筆記所包含的N階 P方陣個數。但如果該階P方陣個數為0則不用輸出。(注意到標點符號要完全一致)

NxN P-square: appear C time(s).

其中N表示P方陣的階數,C表示N階P方陣在該頁中出現的次數。
如果該頁筆記中找不到任何一個二階以上的P方陣,則輸出一列:

No P-square exists.

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
6 6
1 2 3 4 3 1
2 1 4 3 2 4
3 4 1 2 1 3
4 3 2 1 2 4
4 3 2 1 2 1
4 4 1 3 1 2
2 2
1 1
1 1

Sample Output :

Page #1:
2x2 P-square: appear 4 time(s).
4x4 P-square: appear 1 time(s).
Page #2:
No P-square exists.

Hint :

Author :

NPSC 2005 國中組決賽 (管理員:sagit)

  Solve it!   Status Forum