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
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 :


aj_254:
20190511 13:06:38
ac in second go easy one. solvable in python

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