Lesson 2

Consider an \(n\times n\) grid in which some cells may be blocked. There are \(k\) labeled robots \(R_{1},\dotsc,R_{k}\) standing in different free cells. Every robot has its own target cell.

Time is divided into steps. During one step, every robot may wait or move to a horizontally or vertically adjacent free cell. All robots move simultaneously subject to the following restrictions:

• two robots cannot occupy the same cell;


• two robots cannot exchange their cells during one step.

A robot may enter a cell from which another robot is leaving, provided that the latter moves to a third cell. Thus, several robots may follow one another or rotate around a cycle.