#Skip to menu

Lattice paths

First read the problem description.

If we take each intersection as a node and each direction as an edge, then we can see that this is just a DAG. To count the possible paths from start to end we can observe than the number of paths of a node is the sum of the number of paths of its children. We do a topological sort of the graph and starting from the bottom right corner we go back calculating the number of paths. Since for each \(v\) the paths of its children have already been calculated, we need to just sum them.

137846528820

Source code of the solution(s):