1254 . 砲打皮皮2
TopCoder
Tags
Description
當你不費吹灰之力的過完了第一關後，沒想到又馬上來了一個『砲打皮皮2』，遊戲規則跟『砲打皮皮』一樣，只不過你上次那把槍耐力值用完了，但是你有了個新道具『強者炸彈』，這顆炸彈可以依照放入的強者物質的多寡調整其爆炸半徑，每放入一單位強者物質，爆炸半徑就會多一單位，現在你擁有k單位的強者物質，你有辦法消滅棋盤上所有的皮皮嗎？
Input Format
輸入可能包含多筆測試資料。
每筆測試資料的第一行有兩個正整數 N, M（1 ≦ N ≦ 1,000，3 ≦ M ≦ N2 ）分別代表棋盤的大小和皮皮的個數。
接下來有 M 行，每行有兩個正整數 X, Y，代表皮皮所在的座標（0 ≦ X, Y ≦ N）。
不會有兩個皮皮在同樣的位子上。
當N = M = 0時，代表輸入結束，聰明的你當然不會對它輸出任何資料。
Output Format
請輸出最少需要多少單位的強者物質，無條件進位到整數位。
Sample Input 1
5 4
0 0
0 1
1 1
1 0
3 3
1 1
2 2
2 3
2 6
0 0
0 2
1 1
1 2
2 0
2 2
4 7
0 0
1 1
2 2
3 4
4 2
0 3
3 0
0 0
0 0
0 1
1 1
1 0
3 3
1 1
2 2
2 3
2 6
0 0
0 2
1 1
1 2
2 0
2 2
4 7
0 0
1 1
2 2
3 4
4 2
0 3
3 0
0 0
Sample Output 1
1
2
2
3
2
2
3
Hints
Problem Source
原TIOJ1254 / INFOR 21st幹部考(prob J)。Problem Setter：peter50216。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |