This problem can be approached greedily. If we consider the leftmost room ~a~, Michael's leftmost chosen room ~b~ might as well be the rightmost possible room such that ~a~ and ~b~ are within ~D~ units of each other, since that'll cover not only room ~a~, but as many more rooms to the right of ~a~ as possible. In particular, if room ~c~ is the rightmost room which is within ~D~ units of room ~b~, then room ~b~ will cover all rooms between ~a~ and ~c~ (inclusive).

Therefore, if we can determine the locations of these ~3~ rooms ~a~, ~b~, and ~c~, then we can add room ~b~ to Michael's list of chosen rooms, and henceforth ignore room ~c~ and all rooms left of it, thereby reducing the problem to only the section of the hallway to the right of room ~c~. At that point, we can repeat this process until there are no more rooms remaining to the right of room ~c~.

The first step is to find room ~a~. Let's define ~a_1~ to be the leftmost character of room ~a~, and ~a_2~ to be its rightmost character (and similarly for rooms ~b~ and ~c~). ~a_1~ is simply the first . in the floor plan. ~a_2~ is then the character before the first # after ~a_1~.

The second step is to find room ~b~. The furthest character in range of room ~a~ is ~a_2+D~. If that character is a ., then it's inside room ~b~, and so ~b_2~ is the character before the first # after ~a_2+D~. Otherwise, room ~b~ must be to the left, so ~b_2~ is the last . before ~a_2+D~. We don't need to find ~b_1~.

The final step is to find room ~c~. The furthest character in range of room ~b~ is ~b_2+D~. We can repeat exactly the same process as above to find ~c_2~. Once again, at that point, we can add ~1~ to the answer (since Michael will need to visit room ~b~), and repeat the process with the remainder of the string to the right of ~c_2~.