Minimum Tools Cleaning

You are given a grid of size \(n \times m\) where each cell is either dirty (represented by 1) or already clean (represented by 0). You also have \(k\) types of cleaning tools. Each tool is described by a 3\(\times\)3 pattern provided as 9 integers in row‐major order. When you apply a tool on the grid at a valid top-left position \((i, j)\) (so that the entire 3\(\times\)3 pattern lies within the grid), every cell covered by a 1 in the tool will be cleaned (its value set to 0).

Your task is to determine the minimum number of tool applications required to clean the entire grid (i.e. make every cell 0). If it is impossible to completely clean the grid, output -1.

Note: A tool may be applied multiple times and the available tools can be selected in any order. The input sizes are small, so a brute force or BFS based state search is acceptable.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) separated by spaces, representing the number of rows, the number of columns of the grid, and the number of tool types respectively.

The next \(n\) lines each contain \(m\) integers (each either 0 or 1) representing the grid.

The following \(k\) lines each contain 9 integers separated by spaces, representing a tool's 3\(\times\)3 cleaning pattern in row‐major order.

outputFormat

Output a single integer. This integer is the minimum number of tool applications required to clean the entire grid, or -1 if it is impossible.

4 4 3
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0 1 0 0 0 0
1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0

4