Да, тут действительно O(k), так как размер стены константен, а алгоритм обработки этой стены не пробегает по клеткам больше двух раз. Жаль в видео не было объяснено, почему собственно алгоритм работает. Нужно бы подчеркнуть, что жадное размещение свитков гарантирует оптимальность и правильность, если мы начинаем с левого верхнего угла. P.S. мы действительно можем скипать уже рассмотренные клетки, не обнуляя те, на которые свиток был помещён, а записывая 8+смещение на следующую необработанную ячейку. Таким образом диапазон [1; 8] будет означать тип клетки, в которую свиток не был помещён, а [9; 15] посещённую клетку со смещением, однако для этой задачи это бессмысленная оптимизация, так как свитки слишком маленькие
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
Да, тут действительно O(k), так как размер стены константен, а алгоритм обработки этой стены не пробегает по клеткам больше двух раз. Жаль в видео не было объяснено, почему собственно алгоритм работает. Нужно бы подчеркнуть, что жадное размещение свитков гарантирует оптимальность и правильность, если мы начинаем с левого верхнего угла.
P.S. мы действительно можем скипать уже рассмотренные клетки, не обнуляя те, на которые свиток был помещён, а записывая 8+смещение на следующую необработанную ячейку. Таким образом диапазон [1; 8] будет означать тип клетки, в которую свиток не был помещён, а [9; 15] посещённую клетку со смещением, однако для этой задачи это бессмысленная оптимизация, так как свитки слишком маленькие