That's more interesting. I have found a solution that is not exactly a formula but a recursive algorithm that can probably be expressed as a formula by the math enclined (not me). Let N <= M. Switch the numbers around if needed, the problem is symmetric. Visualize it with M on the horizontal for the explanation:
The line touches at least M blocks since it traverses the horizontal. For each of these M blocks, it also touches an additional block whenever it crosses the boundary between two vertical blocks. This happens if and only if the line does not also cross a horizontal boundary at the same time (the intersection of two lines on the grid). So if the line never crosses at an exact intersection, we can add N-1 blocks and the solution is M + N - 1.
If however the line crosses at an exact intersection, the problem is reduced to a smaller one: an integer number of smaller grids. For example, the solution for a 2x10 grid is twice the solution for a 1x5 grid (10); the solution for a 5x10 is five times the solution for a 1x2 (also 10). How to identify this?
If N and M have no common factors (if N/M does not simplify) then the line does not cross any exact intersection and we subtract nothing. The answer is M + N - 1.
If on the other hand N/M simplifies then let P/Q be the simplified ratio and F the factor (N/P). This is a decomposition of the problem into F smaller grids of size P x Q. We solve recursively for one P x Q grid and multiply by F. For this case, the answer is F * (P + Q - 1).
