Matrix Permutations

There is a grid with $N$ rows and $M$ columns. There are $K$ cannons (numbered $1$ through $K$) placed in $K$ cells of this grid. Each cannon can fire a ball to any cell whose Manhattan distance from the cannon does not exceed the strength of the cannon (including the cell with the cannon). Initially (at the $0$-th second), the strengths of all the cannons are $0$ and they increase by $1$ every se