9(I):

Use f_i, j, k to represent the shortest distance to current_row , current_col and start_row.

It is easy to deal j = k . When j ≠ k, we can find the path is from one position along some row's end, and it happens only j or k key used. So we have to handle the up and down when start_row is useful. My approach is to divide every nodes to two, one represents it is going to jump to some row with small length. When use k key, it is possible for position (i, j) to go to the end of k row meets max_{k ≤ t < i}(length(row_t)) < j .Position (i, j) can go to the place where (i, j - 1) can reach, so we link (i, j) -  > (i, j - 1).And we can use monotonic stack to reduce the edge to O(n). And another node represent it jumps to nearest row with same j.

Finally, we can use shortest algorithm to get the distance and path.