BubbleDream's blog

By BubbleDream, history, 17 months ago, In English,

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.

Read more »

  • Vote: I like it
  • +12
  • Vote: I do not like it

By BubbleDream, history, 19 months ago, In English,
  • Vote: I like it
  • -3
  • Vote: I do not like it