KOZE - Sheep
Mirko has a herd of sheep, surrounded by fences backyard. While he was asleep, wolves have sneaked into the fenced area and attacked the sheep.
Backyard is of a rectangular shape, and consists of fields arranged in rows and columns.
- Character '.' (full stop) represents a blank field.
- Character '#' represents a fence.
- Character 'k' represents a sheep.
- Character 'v' represents a wolf.
Two fields belong to the same sector if we can move from the field A to the field B without going over the fence, by making only horizontal and vertical steps (we cannot move diagonally).
If we can escape from field A from the backyard, that field does not belong to any sector.
Luckily, Mirko taught his sheep Kung-Fu skills, and they can defend themselves against wolves only if they outnumber the wolves in that sector. When there are more sheep in the sector than wolves, all wolves die without sheep casualties. Otherwise all sheep perish and wolves are unharmed. If a field doesn't belong in any sector, sheep will flee and wolfs will be left without a prey, so every animal survives.
Write a program that will determine how many sheep and wolves will survive this bloody night.
Input
Integers N and M, number of rows and columns which represent Mirko's backyard.
In every of the N lines, there are M characters representing the appearance of Mirko's backyard - positions of the fences, wolves and sheep.
Constraints
3 <= N, M <= 250
Output
In the first and the only line, print the number of sheep and wolves that will survive.
Example
Input:
8 8
.######.
#..k...#
#.####.#
#.#v.#.#
#.#.k#k#
#k.##..#
#.v..v.#
.######. Output: 3 1
hide comments
sulemank9519:
2022-08-01 21:36:31
I got multiple wrong answers(TLE) just because i was adding new line after printing the result. |
|
sky08:
2022-01-21 17:10:39
Loved problem, for simple and concise. |
|
kunal0403:
2021-11-24 14:06:28
Wtf my wrong solution that does not considers sheeps escaping from the field gets accepted but my correct solution that considers that case gets WA. |
|
rushi2001:
2021-04-07 08:27:52
Took 1 Hour for AC
|
|
tarun_28:
2020-09-21 12:23:51
In case of equal count, all sheep perish and wolves are unharmed.. unfair;) |
|
sting_2_0_0_1:
2020-05-19 11:27:52
AC in one GO !! DFS + Connected components |
|
majd211:
2020-02-22 02:13:30
easy dfs :) |
|
scolar_fuad:
2019-06-09 14:55:11
Ac in one go use directional bfs and don't compare for boundary sheef and wolf ...hopefully you will get AC |
|
anshuman16423:
2019-04-15 20:04:53
https://github.com/anshuman16423/SPOJ-Input-methods-python
|
|
Dương Bảo:
2018-01-19 13:26:28
for those who still getting NZECs with py3, you should try to ignore leading blank lines before reading n and m. |
Added by: | Erik Lončarek |
Date: | 2012-12-02 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Croatian Regionals 2005 |