Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.

А теперь, знатоки, внимание, вопрос: у этой задачи существует детерминированное решение? То есть такое, которое гарантированно решит задачу в поставленных условиях за конечное время? Например, можно случано бродить по полю бесконечное время, и тогда задача будет решена, потому что для любой достижимой клетки вероятность перехода в неё будет ненулевой. Или же можно случайно бродить по полю, ограничив число итераций. Тогда программа завершится в конечное время, но результат будет вероятностным (посетили ~ X% поля).

Вопрос был задан на собеседовании в одной из компаний FANG, и я был очень удивлён, потому что компания каждый год кричит: "Мы больше не задаём задачи про люки и т.д., учите алгоритмы, и будет вам счатье!". Я ничего не имею против нестандартных задач, просто не люблю, когда нарушаются правила игры. Если же у этой задачи есть детерминированное решение, значит у меня где-то пробел в знаниях.

	Мой подход
	Во время собеседования я остановился на том, что нужно собрать достаточный набор признаков, чтобы можно было отличать различные состояния, когда мы попадаем в одну и ту же клетку. Например, смещение клетки относительно старта + направление движения. Тогда придумав какое-нибудь нехитрое правило передвижения (например, правило "правой руки"), можно бродить до тех пор, пока мы не попадём в состояние, в которое уже попадали. Альтернативным подходом было бы запустить несколько роботов, каждый из которых будет действовать отлично от других. Тогда условиев завершения будет встреча роботов в одной и той же клетке. Но тут снова всё упирается в правило обхода, а доказать корректность для каких-то тривиальных правил я не смог за отведённое время. К сожалению, изрядную часть времени собеседования я потратил на размышление о том, стоил ли искать точный алгоритм или может лучше придумать хорошую эвристику?

Вообщем, такие задачи и так никто не любит кроме олимпиадников, а когда ещё непонятно, в какую область стоит углубляться, то совсем грустно становится. Если вы собеседуете, то не надо так.