Is there an easy algorithm to
a) count the number of equivalent shortest paths on a manhattan grid
b) enumerate them systematically?
I wrote a dumb random algo and I could run it for a long time to count unique paths but I imagine there's a closed-form solution?
Conversation
I'm actually interested in a second-order problem: count the fraction of paths that go through a particular segment. If you walked to work on a manhattan grid everyday, making random choices, how long before you walked a specific block? A specific sequence of blocks?
5
1
6
Replying to
Subdivide the problem. Path from start to segment start. Path from segment end to end.
2
2

