maze-type of puzzle

Is this for a course?

First thing you need to do is create a function that evaluates a greenhouse scheme and tells you its cost, using the prescribed cost function (10 + width * height).  Include a parameter 'c' for the added cost of each strawberry that is not covered.

Create another function that adds a random greenhouse to a greenhouse scheme.  It has to make sure the greenhouse doesn't overlap other greenhouses, and make sure you don't add any beyond the maximum allowed number.

Create another function that deletes a random greenhouse from a greenhouse scheme.  If the scheme is already empty, don't worry about it.

Create another function that tweaks a random greenhouse, moving one of its edges by one unit.  If it would cause an invalid greenhouse (zero area) or an overlapping greenhouse, then just don't do it.

Now you're ready to do a simple nondeterministic greedy method to find a decent solution.

If every strawberry must be covered, the contribution of the  $1 per unit of area covered is fixed,
and only the $10 cost of each greenhouse can change, so the best number of greenhouses to build is the minimum possible.
You can start trying to cover everything with 1 rectangle, then with 2 rectangles, etc. stopping as soon as you succeed.
To determine whether it is possible to cover everything with n rectangles without overlap,
it suffices to check every combination of upper left corners and lower right corners.
Some speedups to this may occur to you too.

The greedy algorithm would be pretty simple.  You start with an empty greenhouse scheme, make a copy, apply 1 to a few random mutations to the copy, then compare the cost of the copy to the original.  If the solution has improved, replace the original with the mutated copy.  Loop until satisfied.

Those functions I outlined would also be a good foundation for a genetic algorithm implementation.  That would be similar to the greedy algorithm, except you keep many originals instead of just one, and probabilistically weed out the higher-cost schemes.

I'm also thinking that it would make sense to slowly ramp up the cost-per-missed-strawberry cost parameter.  If it is too big at the beginning, then it will just pick one huge greenhouse to cover up the whole field.  If it is too small at the end, then the greenhouses will not be covering all the strawberries.  So, start with a small cost (15 per missed strawberry or so), then slowly ramp it up (linearly? exponentially?  I don't know...) until it gets to be 10000 or so at the end, to make any incomplete solutions unlikely to survive.

As ozo said, you want to minimize the number of greenhouses.  That implies you want to make as many large greenhouses as possible.

One idea might be to first se what the largest greenhouse is that you can make, then repeat that again and again.

One way to find the largest greenhouse is to try starting at every x,y where these is a strawberry, see if you can stretch as far as you can to the right and down while still enclosing all strawberrys.  Note the size and go to the next x,y.  When you've scanned them all, choose the largest greenhouse and mark all those spots.  Repeat the whole deal until all the strawberrys are covered.

There may be a better way, or flaws in this method, but that's the best I can dream up right now.

That 'C' greenhouse in the example does not look right according to the conditions stated. Are the walls allowed to warp? The Adam solution of one to cover the whole thing sounds best, except it should only extend to the strawberry edge limits. Of course if just one plant would hang outside to provoke an excessive extension, it may need some tweaks. It should have a routine to crunch the difference between one and two structures in a field like this:

@@@@@@@@@@@@@@
@@@@@@@@@@@@@@
@@@@@@@@@@@@@@
@@@@@@@@@@@@@@
         @