TopCoder

User's AC Ratio

87.5% (21/24)

Submission's AC Ratio

29.7% (58/195)

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 6000 65536 262144 1
1 6000 65536 262144 2
2 6000 65536 262144 3
3 6000 65536 262144 4
4 6000 65536 262144 5
5 6000 65536 262144 6
6 6000 65536 262144 7
7 6000 65536 262144 8
8 6000 65536 262144 9
9 6000 65536 262144 10