Consider the n rows and m columns as n+m nodes in a graph. The cell (i,j) with regular (non-magic column) means there is an edge connecting node i to node n+j. A magic column at cell (i,j) means the path goes through the i->(n+j) edge. Now the problem is to find the shortest path from node 1 to node n.

Consider all possible subset of the k important squares. There are at most 2^k <= 2^7 = 128 possibilities.