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
billoybillyboy:
20160414 04:10:15
Easy problem, AC on first go, my first ;) 

dsaini17:
20160209 17:03:08
AC in one go ! [spoiler] Last edit: 20161021 15:06:04 

Mohd Ausaf Jafri:
20160124 10:19:09
minimising the memory!!! cost 5 seg fault 

aditya730:
20160115 17:56:39
For these getting WA read the problem carefully and focus on the two conditions necessary for a valid maze.Any graph traversal, algorithm,preferably bfs should work. Last edit: 20160115 19:08:58 

Carson Kreppein:
20160113 17:39:26
Easy Problem, my 10th ;D 

deepak bhagat:
20151228 18:41:31
finally !! :) 

Anubhav Gupta:
20151102 06:03:58
Input contains spaces!!! lots of WA's because of that 

jarvis:
20151024 12:16:39
Detained from class tests :P :P AC :D here! 

hardik agrawal:
20151023 13:47:36
first bfs! nice problem... my 101st.. :) 

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

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