Que tal isso ...
Dê a cada célula um link para cada um de seus vizinhos. Dê a cada célula algum tipo de nome (isto é, "0/0", "-10/0" (Suponha que você comece em 0,0)). Adicione um HashSet com todos os nomes nele. Ao tentar mover para outra célula, apenas verifique se o vizinho ainda não existe no HashSet.
Além disso, se você criar uma abertura para outra sala, isso significa que as salas existem? Então você criaria um link para uma sala vazia sem links para qualquer sala. Você provavelmente também gostaria de verificar os vizinhos novos quartos. Se existir um, e se abrir para o seu novo quarto, adicione uma porta a esse quarto.
Empty
(0,1)
--- --- ----------
| | | |
0,0 1,0 2,0 Empty
| | | | (3,0)
--- --- ---------- --- ---
| | | | | |
| 0,-1 1,-1 2,-1 Empty
| | | | | | (3,-1)
--- --- --- --- ----------
Empty Empty
(0,-2) (1,-2)
HashSet = {0 | 0, 1 | 0, 2 | 0, 3 | 0, 0 | -1, 1 | -1 ....}
1,0: W = 0,0 / porta; 1,0: N = 1,1 / Vazio; E = 2,0 / porta; S = 1, -1 / parede
Você também precisa garantir que cada quarto novo seja entregue a pelo menos uma porta não adjacente (para outra sala) para que o labirinto possa crescer nessa direção.