An Interesting Task

Revision en4, by BubbleDream, 2019-01-14 15:07:35

Given a grid of size 3 x n (n <= 10^5), consists of empty cells (marked with dot '.'), occupied cells (marked with sharp '#'), asterisks (marked with '*'), and many character 'S' and 'T'. A path connecting S and T is good if the following conditions hold:

  • It doesn't pass through any other S and T.

  • It doesn't pass through occupied cell ('#')

  • It passes through at most 1 asterisk.

Moreover, paths are not allowed to intersect each other. From a cell you can only go to a cell sharing an edge to current cell. Calculate the maximum number of path in the grid.

I haven't got any idea for this problem. Thank you and appreciate for any help.


  Rev. Lang. By When Δ Comment
en4 English BubbleDream 2019-01-14 15:07:35 71
en3 English BubbleDream 2019-01-14 14:57:23 2 Tiny change: 'ked with '"'), and ma' -> 'ked with '*'), and ma'
en2 English BubbleDream 2019-01-14 14:56:56 8
en1 English BubbleDream 2019-01-14 14:56:28 599 Initial revision (published)