In the game Stardew Valley, farming is essential. In order to plant seeds, one must till the soil using a hoe. A golden hoe is an upgraded hoe that allows the player to till 1, 3, or 5 squares of dirt with 1 swing in front of the player. After the soil is tilled and the seeds planted, sprinklers water the 8 squares surrounding the sprinkler. A sprinkler in the path of the hoe's swing will be destroyed and must be avoided. Swings outside of the sprinklers' spray radius are allowed.
Question: Given a pattern of sprinklers, what is the least amount of swings (with the golden hoe) required to till all the soil reachable by the sprinkler(s).
For example, a pattern could be the following:
Which can be simplified to:
The red squares indicate sprinklers and must be avoided in a swing. The empty squares indicate the squares reachable by the sprinklers. Anywhere else is empty space not reachable by the sprinklers, but can still be tilled.
Here is an example of a 5-square swing (the sprinkler in the green square will be destroyed):
What I've tried:
Very basic graph theory using adjacency matrices and connectivity. But failed to take in account the sprinklers and that swings cannot be diagonal.
Change of perspective by viewing the answer as a way to partition the sprinkler pattern into 1-square, 3-square, or 5-square swings.
Maybe graph theory is not the right way to approach the problem?
Here's an approach from Brian Tung's method of selecting squares ''which must be cleared with a separate use of the hoe."
Mark each of the four squares horizontally or vertically adjacent to each sprinkler. Those four squares around a given sprinkler require four hoe swings. The minimum number for the entire system is then a question of how many of these marked squares can be covered in well-placed longer swings.
Here's your example with the 12 squares marked $\fbox{x}$:
\begin{matrix} \square & \fbox{x} & \square & & & & \square & \fbox{x} & \square\\ \fbox{x} & S & \fbox{x} & \square & \fbox{x} & \square & \fbox{x} & S & \fbox{x} \\ \square & \fbox{x} & \square & \fbox{x} & S & \fbox{x} & \square & \fbox{x} & \square \\ & & & \square & \fbox{x} & \square \end{matrix}
The savings comes from three swings of 5 squares, one covering 3 marked squares, the other 2 each. Tilled squares outside the watered area are marked with parentheses.
\begin{matrix} & \square & \fbox{x} & \square & & & & \square & \fbox{x} & \square\\ & \fbox{x} & S & \fbox{1} & \fbox{1} & \fbox{1} & \fbox{1} & \fbox{1} & S & \fbox{x} \\ (2) & \fbox{2} & \fbox{2} & \fbox{2} & \fbox{2} & S & \fbox{3} & \fbox{3} & \fbox{3} & \fbox{3} & (3) \\ & & & & \square & \fbox{x} & \square \end{matrix}
The 5 remaining marked squares $\fbox{x}$ each require their own swing, which can be chosen to cover all the watered squares (with no sprinkler damage).