## The Problem:

A zoological museum can be represented as a matrix in which each cell is a room. The alarm system in the museum allows visitors to go from each room only in one direction, specific to that room.

One night the exhibits went mad and messed the alarm system up. Now there are *traps* in the museum. A room is considered to be a *trap* if it’s impossible to leave the museum starting from it. A person leaves the building once he leaves the rectangle that represents it.

Given the museum’s configuration, find the number of *traps* in it.

**Example**

For

```
museum = [['U', 'L'],
['R', 'L']]
```

the output should be

`trapRooms(museum) = 2`

.

There is no exit if you start from either of the bottom rooms.

Check out the image below for better understanding:

**Input/Output**

**[time limit] 4000ms (py)**

**[input] array.array.char museum**A non-empty rectangular matrix. The possible values of

`museum[i]`

are:`'L'`

if it’s possible to move to the left;`'R'`

if it’s possible to move to the right;`'U'`

if it’s possible to move up;`'D'`

if it’s possible to move down.

*Guaranteed constraints:*

`1 ≤ museum.length ≤ 10`

,

`1 ≤ museum[0].length ≤ 10`

.**[output] integer**The number of

*traps*.

## The Solution:

def trapRooms(museum): x=[[0]*len(museum[0]) for x in range(len(museum))] def rec(a,b,x): if not(a<len(museum) and a>=0 and b<len(museum[0]) and b>=0): return 0 if x[a][b]: return 1 s=0 x[a][b]=1 if museum[a][b]=='U': s+=rec(a-1,b,x) if museum[a][b]=='D': s+=rec(a+1,b,x) if museum[a][b]=='L': s+=rec(a,b-1,x) if museum[a][b]=='R': s+=rec(a,b+1,x) x[a][b]=0 return s p=0 for a in range(len(museum)): for b in range(len(museum[0])): p +=rec(a,b,x) print p return p

## The Explanation:

We need to traverse the maze starting from each o the rooms and see if we can go outside, or go back to one of the rooms we have already passed. If we see any rooms we have already passed, that means we are stuck in the maze because the same room will always cause us to go back to same route.