Abridged problem statement. There is a R × C grid of characters ‘#’ and ‘.’ and a ship
that can only navigate the ‘.’ tiles. The ship can move in the four main directions. You know
some of the last M movements of the ship, the others are marked with ‘?’. Find out the number
of possible positions the ship could currently be at.
R, C <= 500 and M <= 5000
example:
5 9 7
…##…
…#.##…#
…#…##
.##…#…
…#…
WS?EE??
answer is : 22
Есть идеи или решение? Где искать подобные задачи? встречалась ли вам примерно такая задача на олимпиадах?