A Note on the Maximum Size of a Rectilinear Maze
Man‐Tak Shing, Michael M. Mayer, Kim A.S. Hefner · 1989
In this paper, we study the problem of searching through an unknown maze by a robot and show that the size of the largest rectilinear maze the robot can explore in at most k steps is bounded by 2k squared + 2k + 1 for mazes with circuits, and is bounded by 4k squared/3 + 8k/3 + 1 for mazes without circuits, Furthermore, we show that the bounds are tight.