Similar to binary-matrix cluster count #DeepakM #DST+fullScan but the connection is modeled differently.
–Original requirements: Input matrix has an object in each cell
- 1 means wall or barrier
- 0 means passage
- 2 means cheese station
Jerry is [x][y]. Tom starts at  and must collect all cheese and deliver to Jerry. Find shortest path. Tom can only move one (U/D/L/R) step at a time.
https://github.com/tiger40490/repo1/blob/cpp1/cpp1/2d/TomJerry.cpp is my half-finished code. It builds a graph connecting all the cells (each a Node object). It’s able to check feasibility. Todo:
- breadth-first walk from Tom to Jerry, without revisiting any node. Hopefully we can discover all possible paths (i.e. collecting all cheese)
- determine the shortest.