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.
