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
mani_kota_18:
20171219 13:12:22
test cases are according to the problem statement.Easy prob


amulyagaur:
20171019 08:20:44
My 200th :) 

longthtran:
20170831 06:20:28
1


stark_attack:
20170815 12:48:51
getting WA on the 5th test case. plz, provide any tricky test case. I have gone through all corner cases but still unable to pass through. 

yara_farid:
20170803 22:00:51
.


gopikrishna_p:
20170618 20:59:23
good problem to try :) [spoiler] figure out base cases ac in 5 th go :) Last edit: 20170802 13:07:16 

candide:
20170412 20:59:56
The problem is well settled and the description is clear although the question being academic. The problem receives a [big spoiler sentence] (i implemented both for comparison purpose). Last edit: 20170802 13:08:15 

anurag_tangri:
20170315 21:24:27
AC :) Just apply [spoiler] Last edit: 20170322 18:44:46 

abhishek181297:
20170315 04:43:26
AC in 1 go . used backtracking.


gboduljak:
20170227 15:30:07
can be solved with backtracking 
Added by:  cegprakash 
Date:  20120511 
Time limit:  0.824s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 