## 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
 hardik agrawal: 2015-10-23 13:47:36 first bfs! nice problem... my 101st.. :) sri: 2015-09-11 09:22:10 #### #... #.## #.## is this valid or not? how? AJEET KUMAR: 2015-08-09 21:00:04 constraint for m and n in question is not valid. take your array size much greater for example 1000. viraj: 2015-06-06 17:57:40 Pay special attention to "(exactly 2 openings in the edges)". Usama: 2015-04-28 14:28:47 what are the answer of these .#. .## and #...# ? Last edit: 2015-04-28 14:32:12 Subrat Singh: 2015-02-26 15:04:16 finally done :) Last edit: 2015-02-27 15:29:33 Malfple: 2014-12-15 13:13:03 I don't get it...Checked overbound already~~WA. Used another absurd checking~~AC Girish Rathi: 2014-09-09 13:39:08 easy one with simple solution Mitch Schwartz: 2014-07-10 17:17:20 @sudharshan G: your brain. sudharshan G: 2014-07-10 17:01:07 where i get this code please help

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