MAKEMAZE  VALIDATE THE MAZE
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 at least one path from the entry point to exit point.
Given a maze, just find whether the maze is "valid" or "invalid".
Input
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
For each test case find whether the maze is "valid" or "invalid".
Constraints
1<=t<=10000
1<=m<=20
1<=n<=20
Example
Input: 6 4 4 #### #... #.## #.## 5 5 #.### #..## ##..# #.#.# ###.# 1 1 . 5 1 # # . . # 2 2 #. .# 3 4 #..# #.## #.## Output: valid valid invalid valid invalid invalid
hide comments
mahbubkuet08:
20211201 18:58:52
AC in 2nd time 

wslord:
20201226 17:50:09
AC in one go....;) 

shubhamnitt:
20201003 19:38:29
pqv907 the test case you provied will output invalid 

jrseinc:
20200813 18:39:34
What am I doing wrong? Like most of the users I'm also getting WA on 5th testcase.


i'm awesome :D:
20200530 20:36:20
My 150th :D 

pqv907:
20200525 08:15:45
If you get WA at 5th TC.


upen3103:
20200427 23:51:26
AC in one go!!! 

dkkv0000:
20200121 09:48:25
1 shot ac 

b1nary_:
20191212 12:52:58
Read the question carefully. Everything is explained there. 

meoconxinhxan:
20191011 03:49:15
Why Map :

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