Answer Happy

PROJECT 7: You have an m x n maze of rooms. Each adjacent pair of has a door that allows passage between the rooms. At some point of time some of the doors are locked, the rest are open. A mouse sits at room number (s, t) and there is fabulous food for the mouse at room number (u, v). Your task is to determine whether there exists a route for the mouse from room (s, t) to room (u, v) through the open doors. The idea is to start a search at room (s, t), then investigate adjacent rooms (sl, tl)......(sk, tk) that can be reached from (s, t), and then those adjacent rooms that be reached from each (si,ti) and so on. H(ij+1) 0.4 1.42.4 3.44.45.4 0.3 1.3 2.3 3.34.35.3 0.2 1.2 2.23.24.25.2 V(ij) V(i+1.j) H(ij) 0.1 1.1 2.1.3.14.1 5.1 0.0 1.0 2.03.04.05.0 In order to set up the notations about indices, look at the above figure. The rooms are numbered (i, j), where i grows horizontally (along the x direction) and j grows in the vertical direction (along the y axis). The four walls of the (i, j)-th room are numbered as shown to the right of the maze. If a horizontal or vertical wall has an open door, we indicate this by the value 1; otherwise, we use the value 0. That is, H(ij) = 1 if the horizontal door connecting the rooms (ij-1) and (ij) is open; H(ij) = 0 otherwise. Similarly, V(ij) is 1 or 0 depending on whether the vertical door between the rooms (i-1.j), and (i, j) is open or not. This scheme also applies to the walls of the boundary of the maze.