Number of Grid Paths With Conditions

Revision en2, by CipherText, 2020-04-24 19:41:36

I have a grid containing $$$10^6$$$ rows and $$$10^6$$$ columns. I also have coordinates of $$$N$$$ cells of this grid each of which has either a red ball, or a blue ball, or both (one ball of each color). When a person visits a cell, he/she can collect all the balls from that cell. The target is to reach the bottom-right cell from the top-left cell by collecting at least one ball of each color. From one cell, it's only possible to visit the cell on its right or the cell below it. Upper bound of $$$N$$$ is $$$1000$$$.

The problem is to find the number of different paths that has at least one cell with blue ball and at least one cell with red ball in it. Two paths are different if there is at least one cell that belongs to only one of them.

How can I solve this efficiently?

Tags grid

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English CipherText 2020-04-24 19:41:36 299 Tiny change: 'l, or both. When a p' -> 'l, or both (one ball of each color). When a p' (published)
en1 English CipherText 2020-04-24 17:58:45 514 Initial revision (saved to drafts)