Remote Training on Programming

На кружке по робототехнике, куда ходит Вася, имеется полигон для испытания собираемых роботов. Полигон представляет собой квадратный стол, на котором расчерчено клетчатое поле размером $$$N \times N$$$ клеток. В некоторых клетках устанавливаются препятствия, и роботы вынуждены их объезжать.

Недавно Вася собрал нового робота, и теперь хочет проверить его работу. Вася помещает робота в клетку с координатами ($$$1$$$, $$$1$$$) и проверяет, сможет ли он добраться до клетки ($$$N$$$, $$$N$$$). За один шаг робот может переместиться в соседнюю по стороне клетку, если в ней нет препятствия. Робот не может выходить за пределы полигона.

Вася хочет разместить препятствия на полигоне так, чтобы кратчайший путь из клетки ($$$1$$$, $$$1$$$) в клетку ($$$N$$$, $$$N$$$) содержал ровно $$$K$$$ клеток. Помогите ему это сделать.