1669 . 征戰天龍國
TopCoder
Tags
Description
你擁有一支強大的陸戰隊。這支陸戰隊的所有士兵排成了一個矩形，如下：
........-+.-++.+...-.+....+-..
.--...+.........++..........+.
...++....+....-+..+..+........
..-..+...-......-.+.++.+..--..
...+.+-.+..-.+.......+....-+.-
......+.+.++.-..++-+..+......-
...+....+..+........-+.-.-+...
...+-..+.+.++.+.........+++...
如果一個士兵的戰力是1，則在軍隊中以「+」表示；如果戰力是-1(會拖累戰役)，
則以「-」表示。至於戰力是0的則用「.」表示。一個軍隊中，可以選出任意一個
矩形區塊的子軍隊，而該子軍隊的戰力就是子軍隊中所有士兵的戰力和。
不幸的是，你將在不久之後與天龍國作戰。為了減低損耗，你決定派最少數量的士
兵出去作戰。藉著神秘消息的幫助，你得知派出去的子軍隊戰力最少要有K以上才
能戰勝。那你究竟要派幾個士兵出去作戰呢？
Input Format
第一行：三個整數H、W、K，代表全軍隊中共有H列、W行。
第二行到第H＋1行：每行會有W個字元，字元只會是「+」、「-」或「.」。
Output Format
第一行：請輸出一個整數p，代表最少要派p個士兵出去。
如果無論如何都無法贏得戰役，請輸出-1。
Sample Input 1
5 5 3
-...-
.+.+.
..+..
.+.+.
-...-
-...-
.+.+.
..+..
.+.+.
-...-
Sample Output 1
6
Hints
佔總分30%的測試資料中，沒有戰力為負的士兵。
佔總分70%的測試資料中，1≦H, W≦300，0≦K≦90,000。
對於所有的測試資料而言，1≦H, W≦500，0≦K≦250,000。
Problem Source
原TIOJ1669 / 建國中學99年校內培訓contest #1 prob 4
problem setter:suhorng
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 |