2011年7月17日 星期日

201 - Squares

一個由點組成的正方形矩陣,例如下圖中的16個點,將部份相鄰的點用垂直線或水平線連接起來後,所組成的圖形如下,之後再計算此圖正方形的數量,例如下圖中,正方形寬度為1的數目共2個,正方形寬度為2的數目共1個,所以共有3個正方形。


本題請你計算圖形中,正方形的數量。

Input

輸入包含多組測試資料,每組測試資料的第一列為整數 n (2 <= n <= 9),表示大正方形的大小,點的數目即為n^2。

輸入資料的第二列為 m,為相鄰兩點的連接線總數,接下來有 m 列,每列為一條長度為1之連接線的資訊,其格式有兩種:

H i j:為一條水平線,在第 i 列上連接第 j 欄到第 j+1欄的水平線。
V i j:為一條垂直線,在第 i 欄上連接第 i 列到第 j+1列的垂直線。

上圖的例子即為範例資料中的第一筆。

Output

每組測試資料請先輸出"Problem #NUM",NUM為測試資料的編號,空一列後請輸出不同正方形大小各別的總數,請由正方形大小由小到大輸出,其格式為"NUM1 square (s) of size NUM2",表示正方形大小為NUM2的數目共NUM1個。若沒辦法連成任一組正方形,請輸出"No completed squares can be found."。每組測試資料間請以兩個空行與一列星號隔開,請參考範例資料。

Sample Input
4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1

Sample Output
Problem #1

2 square (s) of size 1
1 square (s) of size 2

**********************************

Problem #2

No completed squares can be found.

原文出處

沒有留言:

張貼留言