We will count $n\!\times\!3$ grids containing no $2\!\times\!2$ block of $1$s ("three-row square-free grids"):
If we encode the columns by integers using the entries as the digits of a binary number, then for three rows, we have three classes of columns: $A=\{0,1,2,4,5\}$, $B=\{3,6\}$ and $C=\{7\}$, with transfer matrix $M=\Big(\begin{smallmatrix}5&2&1\\5&1&0\\5&0&0\end{smallmatrix}\Big)$.
The number of three-row square-free grids is thus the sum of the entries in the vector $$(5,2,1)\,M^{n-1}.$$
The closed form is complex, involving roots of cubic polynomials.
The first few terms are $8, 57, 417, 3032, 22077, 160697, 1169792, 8515337, 61986457, 451223152$. This is A181246 in OEIS.
Alternatively, if we let $a(z)$, $b(z)$ and $c(z)$ be the (ordinary) generating functions for $n\!\times\!3$ square-free grids where the final column is in classes $A$, $B$ and $C$ respectively, and we let $g_3(z)$ be the OGF for all three-row square-free grids, then solving the equations
$$\begin{array}{rcl}a(z) &=& 5 z + z\:\! (5 a(z) + 5 b(z) + 5 c(z))\\ b(z) &=& 2 z + z\:\! (2 a(z) + b(z))\\c(z) &=& z + z\:\! a(z)\\g_3(z)&=&a(z)+b(z)+c(z)\end{array}$$
gives
$$g_3(z)\;=\;\frac{z\:\! (8 + 9 z - 5 z^2)}{1 - 6 z - 10 z^2 + 5 z^3}.$$
For four-row grids, five classes are required, with transfer matrix $\left(
\begin{smallmatrix}
8 & 4 & 1 & 2 & 1 \\
8 & 2 & 1 & 1 & 0 \\
8 & 4 & 0 & 0 & 0 \\
8 & 2 & 0 & 0 & 0 \\
8 & 0 & 0 & 0 & 0
\end{smallmatrix}
\right)$, giving generating function $\frac{8 z (2+7 z+z^2-8 z^3)}{1-10 z-54 z^2-16 z^3+64 z^4}$.
There are many numerical results in OEIS: three rows, four rows, five rows, six rows, seven rows, eight rows, and nine rows.
Best Answer
It looks like $n \times m$ are the dimensions of rectangle, so the grid of points is $(n+1) \times (m+1)$. Your answer is not correct. Take a $1,2,\sqrt 5$ triangle, which gives $s=2,t=1$ for the covering rectangle. If the $2$ is along the $n$ direction, there are $n-1$ places it can start and $m$ places you can start the other way, so there are $(n-1)m$ triangles. The triangle has two orientations in the rectangle, so this gives $2(n-1)m$ triangles. This matches your formula, but you can orient the rectangle the other way and get another $2(m-1)n$ triangles.
I don't have a magic way to find $s,t$. First see if any of $a,b,c$ are irrational. Find all the ways to express $a^2,b^2,c^2$ as a sum of two squares. You need to close the triangle, so need to find a way to add or subtract the values in your expression to do so. For example, if we have a $5,12,13$ triangle, we have $5^2=5^2+0^2=3^2+4^2, 12^2=12^2+0^2, 13^2=13^2+0^2=5^2+12^2$. The fact that $12^2$ has no other expression says that the $12$ must be along a grid line. Then you find $s=5,t=12$.
If you have a triangle with $a=10,b=13$, both of which can be put orthogonally or diagonally, the third side will tell you which. If your triangle is $10,13,\sqrt{269}$,the fact that $269=10^2+13^2$ says the $10$ and $13$ are orthogonal. If your triangle is $10,13,\sqrt {333}$, you have $333=18^2+3^2$. If the $10$ is oriented with the $6$ vertical and $8$ horizontal, the $13$ must be oriented with the $12$ vertical so $12+6=18$ and the $5$ horizontal so $8-5=3$
I don't know if there are triangles that can have more than one orientation on the grid up to rotations and reflections.