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
s1234: 2016-07-23 03:29:53

More than two opening even if they are not connected will cause invalid:
##.#
.#.#
##.#
##.# is invalid.

rushikesh: 2016-07-07 05:25:20

17238184 my code id . please can someone tell me what is wrong with my code it hits me with SIGSEGV error

fadi_yns: 2016-06-22 07:28:40

sir, its valid cause you have exactly one entry point and exactly one exit point and there is a path between this tow points

billoybillyboy: 2016-04-14 04:10:15

Easy problem, AC on first go, my first ;)

dsaini17: 2016-02-09 17:03:08

AC in one go ! [spoiler]

Last edit: 2016-10-21 15:06:04
Mohd Ausaf Jafri: 2016-01-24 10:19:09

minimising the memory!!! cost 5 seg fault

aditya730: 2016-01-15 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: 2016-01-15 19:08:58
Carson Kreppein: 2016-01-13 17:39:26

Easy Problem, my 10th ;D

deepak bhagat: 2015-12-28 18:41:31

finally !! :)

Anubhav Gupta: 2015-11-02 06:03:58

Input contains spaces!!! lots of WA's because of that


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