2013年7月9日星期二

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，所以他希望用最少的砲彈個數去殺死所有在聖殿中的敵人。

每個聖殿為一個 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

每行測資輸出一行，第一個印出 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

Unfortunate狗的ACM園地