TopCoder

Thumb   5
Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

31.8% (7/22)

Description

你擁有一支強大的陸戰隊。這支陸戰隊的所有士兵排成了一個矩形,如下:

........-+.-++.+...-.+....+-..
.--...+.........++..........+.
...++....+....-+..+..+........
..-..+...-......-.+.++.+..--..
...+.+-.+..-.+.......+....-+.-
......+.+.++.-..++-+..+......-
...+....+..+........-+.-.-+...
...+-..+.+.++.+.........+++...

如果一個士兵的戰力是1,則在軍隊中以「+」表示;如果戰力是-1(會拖累戰役),
則以「-」表示。至於戰力是0的則用「.」表示。一個軍隊中,可以選出任意一個
矩形區塊的子軍隊,而該子軍隊的戰力就是子軍隊中所有士兵的戰力和。

不幸的是,你將在不久之後與天龍國作戰。為了減低損耗,你決定派最少數量的士
兵出去作戰。藉著神秘消息的幫助,你得知派出去的子軍隊戰力最少要有K以上才
能戰勝。那你究竟要派幾個士兵出去作戰呢?

Input Format

第一行:三個整數H、W、K,代表全軍隊中共有H列、W行。
第二行到第H+1行:每行會有W個字元,字元只會是「+」、「-」或「.」。

Output Format

第一行:請輸出一個整數p,代表最少要派p個士兵出去。
如果無論如何都無法贏得戰役,請輸出-1。

Sample Input

5 5 3
-...-
.+.+.
..+..
.+.+.
-...-

Sample Output

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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 6000 65536
1 6000 65536
2 6000 65536
3 6000 65536
4 6000 65536
5 6000 65536
6 6000 65536
7 6000 65536
8 6000 65536
9 6000 65536