Имеем карту с лабиринтом произвольным и, соответственно, сетку AxB. Надо провести объект размером NxN (N>1) по лабиринту, учитывая, что ширина прохода может быть меньше N. Вопрос: как избежать захода в "узкие места"?

Den_diвсе узкие места закрашиваем, что туда нет прохода(как стенка), а далее по правому краю до упора, или что вам надо.
Каким образом закрасить? Перебором по всей матрице проверять "свободность" группы клеток? Или есть способ "подешевле"?

Что значит провести? Вручную что-ли?
Провести с учетом "ширины". А ведет А*.

2 Aklin
он щупает соседние клетки и ничего не знает о "ширине" прохода, т.е. объект, идущий по лабиринту может быть по размерам больше одной клетки. Простейший пример: имеем сетку 5х5 см на полу, входную дверь шириной 100см или 20 клеток в квартиру и большой шкаф шириной, скажем, 30 клеток (проекция на пол). Ясен пень, что не пронести. Значит надо искать другой проход.
Пока докумекал до "нормализации" карты путем накладывания на каждую ячейку матрицы 2х2 (частный случай) для проверки пересечения со стенами. Таким образом вроде бы все проходы шириной в 1 клетку блокируются, остаются только более широкие. В принципе алгоритм одноразовый, можно, наверно, забить на производительность.

Aklinщупайте не 1 клетку, а правое и левое значение (вершнее и нижнее)...

или если все М клеток путы, двигайтесь.

или еще и разварачиваться нужно?

Нет, разворачиваться не надо. Модифицировать уже написанный поиск лень, поэтому просто нормализую карту как написал выше и подсовываю ее А* :)
Пожалуй на этом варианте остановлюсь.