## MAKEMAZE - VALIDATE THE MAZE

MAZE MAKING

There are many algorithms to generate maze. (http://en.wikipedia.org/wiki/Maze_generation_algorithm). After generating the maze we’ve to validate whether it’s a valid maze or not. A valid maze has exactly one entry point and exactly one exit point (exactly 2 openings in the edges) and there must be atleast one path from the entry point to exit point.

Given a maze, just find whether the maze is "valid" or "invalid".

Input Specification:

The first line consists of an integer t, the number of test cases. Then for each test case, the first line consists of two integers m and n, the number of rows and columns in the maze. Then contains the description of the matrix M of order mxn. M[i][j]=# represents a wall and M[i][j]='.' represents a space.

Output Specification:

For each test case find whether the maze is "valid" or "invalid".

Input Constraints:

1<=t<=10000

1<=m<=20

1<=n<=20

Sample Input:

```6
4 4
####
#...
#.##
#.##
5 5
#.###
#..##
##..#
#.#.#
###.#
1 1
.
5 1
#
#
.
.
#
2 2
#.
.#
3 4
#..#
#.##
#.##
```

Sample Output:

```valid
valid
invalid
valid
invalid
invalid
```

hide comments
 < Previous 1 2 3 4 5 6 7 Next > mani_kota_18: 2017-12-19 13:12:22 test cases are according to the problem statement.Easy prob amulyagaur: 2017-10-19 08:20:44 My 200th :) longthtran: 2017-08-31 06:20:28 1 5 4 #..# #.## #..# #..# #### valid stark_attack: 2017-08-15 12:48:51 getting WA on the 5th test case. plz, provide any tricky test case. I have gone through all corner cases but still unable to pass through. yara_farid: 2017-08-03 22:00:51 . Last edit: 2017-08-07 10:31:15 gopikrishna_p: 2017-06-18 20:59:23 good problem to try :) [spoiler] figure out base cases ac in 5 th go :) Last edit: 2017-08-02 13:07:16 candide: 2017-04-12 20:59:56 The problem is well settled and the description is clear although the question being academic. The problem receives a [big spoiler sentence] (i implemented both for comparison purpose). Last edit: 2017-08-02 13:08:15 anurag_tangri: 2017-03-15 21:24:27 AC :) Just apply [spoiler] Last edit: 2017-03-22 18:44:46 abhishek181297: 2017-03-15 04:43:26 AC in 1 go . used backtracking. Thanks @s1234 for the hint . Key point ... More than two opening even if they are not connected will cause invalid: ##.# .#.# ##.# ##.# is invalid. Last edit: 2017-03-15 04:44:56 gboduljak: 2017-02-27 15:30:07 can be solved with backtracking

 Added by: cegprakash Date: 2012-05-11 Time limit: 0.824s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 GOSU