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:
20151023 13:47:36
first bfs! nice problem... my 101st.. :) 

sri:
20150911 09:22:10
####


AJEET KUMAR:
20150809 21:00:04
constraint for m and n in question is not valid. take your array size much greater for example 1000. 

viraj:
20150606 17:57:40
Pay special attention to "(exactly 2 openings in the edges)". 

Usama:
20150428 14:28:47
what are the answer of these


Subrat Singh:
20150226 15:04:16
finally done :) Last edit: 20150227 15:29:33 

Malfple:
20141215 13:13:03
I don't get it...Checked overbound already~~WA. Used another absurd checking~~AC 

Girish Rathi:
20140909 13:39:08
easy one with simple solution 

Mitch Schwartz:
20140710 17:17:20
@sudharshan G: your brain. 

sudharshan G:
20140710 17:01:07
where i get this code please help

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