>>94009
Про тебя комикс.
Если обсуждать вкусовщину, то я бы сделал как-то так: http://pastebin.com/UibXEbV1. Мне не нравятся постоянные lab[p[0]][p[1]] и преобразования из пары точек в букву-направление и назад.

Но есть и настоящая проблема.
Твой код очень долго работает на лабиринтах вида:

>check_route(checkio, [

> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],

> [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],

> [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1],

> [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

> [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

> [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

> [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

> [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

> [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

> [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

> [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])

Во всяком случае, превышает ограничение по времени на ideone.
Дело в том, что ты написал алгоритм с экспоненциальной сложностью, иными словами, в худшем случае он переберёт все возможные пути. Количество таких путей в пустом лабиринте — порядка 3^cells (в среднестатистическую клетку мы приходим из соседней и остаются 3 варианта следующего шага). В примере рекурсия доходит вниз до упора, и затем ей предстоит долгий и увлекательный перебор всех ~3⁶⁴ путей в тупике 8 × 8, единственный выход из которого она сама же и перекрыла.

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

>9: path = ''

>+ seen = []

>10: graph(start, end, done, path, maze_map)

>＊ graph(start, end, done, path, maze_map, seen)

>14: def graph(start, end, done, path, maze):

>＊ def graph(start, end, done, path, maze, seen):

>16: done.append(start)

>+ seen.append(start)

>23: if step not in done:

>＊ if step not in done and step not in seen:

>27: graph(start, end, done, path, maze)

>＊ graph(start, end, done, path, maze, seen)

(шутка про Джона Сину или https://www.youtube.com/watch?v=F70pCctSi0o
https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Поиск_в_глубину#Python — собственно, ex выполняет ту же функцию, так что с исправлением алгоритм превращается в обычный поиск в глубину.

P.S. Строки в питоне неизменяемые («изменение» сводится к созданию новой), и если list.append(x), действительно, будет видно отовсюду, то path += x — всего лишь синоним path = path + x, который ничего, кроме этой ссылки на path, не затронет. Поэтому делать [:len] бессмысленно.