Я так понимаю, связность лабиринта гарантируется?

Я знаю, как придумать такую строку. Рассмотрим всевозможные ситуации (ситуация = лабиринт + клетка, в которую мы попали).

Рассмотрим первую ситуацию и выпишем последовательность, которая позволит нам пройти все клетки в этой ситуации. При этом во всех остальных ситуациях наблюдаем, где мы оказались.

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

И так далее.

О положении стен нам ничего неизвестно?

Рассуждая примерно как здесь, можно получить, что случайная строка длины (возможно, степень логарифма неправильная, это навскидку) с высокой вероятностью подходит для всех лабиринтов и для всех стартовых положений.

UPD: здесь n -- количество вершин, если n -- размер лабиринта, то длина равна .

Задача B с NEERC 2008 (http://codeforces.net/gym/100286) похожа на вашу. У нас зашёл рандом, но там ограничения уж совсем маленькие по-моему. P.S: там интерактив, решать можно совсем не рандомом, т.к. мы ещё получаем информацию, попали ли мы в стену. Но для проверки решения (если Вы не взяли эту задачу откуда-то, а придумали сами) вполне сойдёт.