2013年7月9日 星期二

11419 - SAM I AM


Problem C
SAM I AM
Input: Standard Input
Output: Standard Output

世界正面臨重大的危機! Mental's forces 將要回到地球並且敲滅人類,我們最後的希望 Sam “Serious” Stone 能夠停止這邪惡的勢力,裝備各種強大的武器後,Serious Sam 開始他的摧毀邪惡勢力任務。

在兩天三夜的奮戰後,Sam 現在在 KOPTOS 聖殿前,Mental 的 Ugh Zan III 正在那裡等著他。但是此時,他面臨一個重大危機,現在聖殿中充滿了敵人,而且也已經彈藥缺乏。在探查聖殿之後,Sam 發現聖殿是一個矩形,而且發現所有敵人的所在位置。


突然間,他意識到他可以不用進入聖殿中,使用大砲發出一個非常巨大的球,並且殺死所有路徑上的敵人,直到它爆炸為止,但是砲彈只能水平或垂直發射。

現在他想要保留最多的彈藥去對付 Mental,所以他希望用最少的砲彈個數去殺死所有在聖殿中的敵人。

Input

每個聖殿為一個 R x  C 的格子,第一行會有三個整數 R(0<R<1001), C(0<C<1001), N(0<N<1000001),R 表示聖殿的行 (row),C 表示聖殿的列 (column),N 表示有多少的敵人位置。接一來會有 N 行,每行會有兩個整數表示敵人的位置。

以 R = C = N = 0 結束程式。
輸入檔案大小約為 1.3 MB

Output

每行測資輸出一行, 第一個印出 m  最小的砲彈數,接著用空白間隔印出砲彈位置。
水平放置的砲彈使用 “r”後接一個行數(row number),垂直“c”後接一個列數(column number)。如果有多組解,任何一組都可以通過。

Sample Input                               Output for Sample Input

4 4 3
1 1
1 4
3 2

4 4 2
1 1
2 2

0 0 0

2 r1 r3
2 r1 r2



Problemsetter: Syed Monowar Hossain
Special Thanks: Derek Kisman