Project: 15 Puzzle, $A^{*}$, and Coordinated Motion Planning · Coordinated Motion Planning
Lesson 5
Programming problem. Given a grid with obstacles and several robots, determine whether all robots can move from their starting cells to their target cells without collisions.
- Input format. The first line contains two integers \(n\) and \(k\) (\(2\le n\le 5\), \(1\le k\le3\)). The next \(n\) lines use \(\texttt{.}\) for a free cell and \(\texttt{\#}\) for an obstacle. Each of the next \(k\) lines contains \(s_{x},s_{y},t_{x},t_{y}\) for one robot; coordinates range from \(0\) to \(n-1\). All starting cells are different, all target cells are different, and all specified cells are free.
- Output format. Output \(1\) if there exists a collision-free schedule that moves every robot to its target, and \(0\) otherwise.
This problem can only be submitted at Cogniterra.
Public sample 1
Public sample 2
Public samples
Input
3 2 ... ... ... 0 0 0 2 0 2 0 0
Expected output
1
Input
3 2 ... ### ### 0 0 0 2 0 2 0 0
Expected output
0