Connection Status:
Competition Arena > GooseInZooDivOne

GooseInZooDivOne

SRM 578 · 2012-12-13 · by snuke

SRM 578 · 2012-12-13 · by snuke · Greedy, Simple Math
Class Name: GooseInZooDivOne
Return Type: int
Method Name: count
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

Crow Keith is looking at the goose cage in the zoo. The bottom of the cage is divided into a grid of square cells. There are some birds sitting on those cells (with at most one bird per cell). Some of them are geese and all the others are ducks. Keith wants to know which birds are geese. He knows the following facts about them:
  • There is at least one goose in the cage.
  • The number of geese is even.
  • Each bird within Manhattan distance dist of any goose is also a goose.
You are given a String[] field and the int dist. The array field describes the bottom of the cage. Each character of each element of field describes one of the cells. The meaning of individual characters follows.
  • The character 'v' represents a cell that contains a bird.
  • The character '.' represents an empty cell.
Return the number of possible sets of geese in the cage, modulo 1,000,000,007. Note that for some of the test cases there can be no possible sets of geese.

Notes

  • The Manhattan distance between cells (a,b) and (c,d) is |a-c| + |b-d|, where || denotes absolute value. In words, the Manhattan distance is the smallest number of steps needed to get from one cell to the other, given that in each step you can move to a cell that shares a side with your current cell.

Constraints

  • field will contain between 1 and 50 elements, inclusive.
  • Each element of field will contain between 1 and 50 characters, inclusive.
  • Each element of field will contain the same number of characters.
  • Each character of each element of field will be 'v' or '.'.
  • dist will be between 0 and 100, inclusive.
Examples
0)
{"vvv"}
0
Returns: 3

There are three possible sets of positions of geese: "ggd", "gdg", or "dgg" ('g' are geese and 'd' are ducks).

1)
{"."}
100
Returns: 0

The number of geese must be positive, but there are no birds in the cage.

2)
{"vvv"}
1
Returns: 0
3)
{"v.v..................v............................"
,".v......v..................v.....................v"
,"..v.....v....v.........v...............v......v..."
,".........vvv...vv.v.........v.v..................v"
,".....v..........v......v..v...v.......v..........."
,"...................vv...............v.v..v.v..v..."
,".v.vv.................v..............v............"
,"..vv.......v...vv.v............vv.....v.....v....."
,"....v..........v....v........v.......v.v.v........"
,".v.......v.............v.v..........vv......v....."
,"....v.v.......v........v.....v.................v.."
,"....v..v..v.v..............v.v.v....v..........v.."
,"..........v...v...................v..............v"
,"..v........v..........................v....v..v..."
,"....................v..v.........vv........v......"
,"..v......v...............................v.v......"
,"..v.v..............v........v...............vv.vv."
,"...vv......v...............v.v..............v....."
,"............................v..v.................v"
,".v.............v.......v.........................."
,"......v...v........................v.............."
,".........v.....v..............vv.................."
,"................v..v..v.........v....v.......v...."
,"........v.....v.............v......v.v............"
,"...........v....................v.v....v.v.v...v.."
,"...........v......................v...v..........."
,"..........vv...........v.v.....................v.."
,".....................v......v............v...v...."
,".....vv..........................vv.v.....v.v....."
,".vv.......v...............v.......v..v.....v......"
,"............v................v..........v....v...."
,"................vv...v............................"
,"................v...........v........v...v....v..."
,"..v...v...v.............v...v........v....v..v...."
,"......v..v.......v........v..v....vv.............."
,"...........v..........v........v.v................"
,"v.v......v................v....................v.."
,".v........v................................v......"
,"............................v...v.......v........."
,"........................vv.v..............v...vv.."
,".......................vv........v.............v.."
,"...v.............v.........................v......"
,"....v......vv...........................v........."
,"....vv....v................v...vv..............v.."
,".................................................."
,"vv........v...v..v.....v..v..................v...."
,".........v..............v.vv.v.............v......"
,".......v.....v......v...............v............."
,"..v..................v................v....v......"
,".....v.....v.....................v.v......v......."}
3
Returns: 898961330
4)
{"v.."
,"..v"
,".v."}
2
Returns: 1

1

Submissions are judged against all 75 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GooseInZooDivOne with a public method int count(vector<string> field, int dist) · 75 test cases · 2 s / 256 MB per case

Submitting as anonymous