Not difficult task. Let's iterate param a. If 12 % a != 0, continue. Calculate b = 12 / a. Let's iterate column (from 1 to b) and for each it's cell (i, j) check, if it contains X or not. Cell (i, j) — is ((i–1) * a + j) -th element of string.
In the final version of statement we must choose all lines we haven't finish already. If it is a string where we have S...G — answer - 1.
Otherwise, the answer is the number of distinct distances, as one step kills all distances of the minimal length.
Let's note that the number of 90 clockwise make sence only by modulo 4. Horizontal — by modulo 2, and 90 counterclockwise — by modulo 4, and 1 such rotation is 3 clockwise rotations.
90 clockwise: newi = j; newj = n–i + 1 don't forget to swap(n, m).
Horizontal: newj = m–j + 1
If the distribution is correct, after deleting all ribs with cost more than 0 graph will transform to components of corrects size. Also, the nodes are numereted so we should turn dfs for the first node of each type and be sure that we receive exact all nodes of this type and no ohter.
Now simple floyd warshall, and put in each cell of adjacent matrix of components the minimal weight between all ribs from 1 component to another.
Let's solve this for each bit separately. Fix some bit. Let's put 1 if the number contains bit and 0 otherwise. Now we receive the sequence, for example 11100111101.
Now let's look on sequence of 1 without 0, for this sequence current bit will be added to the sum on the first stage (with all numbers single) on the second stage (with all neighbouring pairs) on the third stage and so on, the number of appiarence for sequence of neighbouring 1 is a formula which depends on the length of sequence only.
The last is to learn how to modificate. For each bit let's save the set of sequence of 1. When the bit is deleted, one sequence is sepereted on two, or decreases its length by 1. When the bit is added, new sequence of length 1 appears, or some sequence increases its lentgh by 1 or two sequence transform to 1 biger sequence.