Seed Bags
InterviewTime limit1sMemory limit1024 MB
Given a garden grid with marked cells, find the fewest 3x3 seed bags, each centered on a garden cell, that cover every marked cell.
- Level
Medium4 of 10
- Topics
- Brute force, Matrix, Greedy
- Solved
- No attempts yet
Problem
Looking at the space you've allotted for your garden, you begin to wonder how many bags of seeds you'll need to buy to fill it. It's a little complicated, though, because you plant seeds in a unique way. To plant, you throw the bag into the air, and the seeds land around you in a 3x3 square. Given the layout of your garden and the areas where you want crops to grow, determine how many bags of seeds are required. If some seeds land where you do not want them, that is fine. You just will not water those. It's also acceptable for an area to be overlapped by multiple bags of seeds.
Input
The first line contains a single integer n, the number of data sets. Each data set starts with a single integer s (1≤s≤8), the side length of the square garden. The next s lines give the layout of the garden. A '.' marks a spot that does not need to be seeded, and an 'x' marks an area where you want to plant seeds.
Output
For each test case, output the minimum number of seed bags needed to plant the garden.