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
meoconxinhxan: 2019-10-11 03:49:15

Why Map :
3 4
#..#
#.##
#.##
is invalid pls help me

Reply: Because there are 3 openings

Last edit: 2019-11-04 13:16:24
aj_254: 2019-05-11 13:06:38

ac in second go easy one. solvable in python

ilham_sr0611: 2019-04-19 14:14:48

Last edit: 2019-04-19 14:15:15
ayushr2: 2018-09-27 22:07:12

How do you see what TCs you pass?

nitish235: 2018-08-26 08:55:32

if you sol is failing for tc 5
try this
1
2 3
.##
.##

Seshadri R: 2018-06-20 05:13:40

Please provide a "delete comment" facility

=(Francky)=> EB members and psetters can do that. Please alert, if you find some message to be deleted.

Last edit: 2018-06-20 10:40:17
mani_kota_18: 2017-12-19 13:12:22

test cases are according to the problem statement.Easy prob

amulyagaur: 2017-10-19 08:20:44

My 200th :)

longthtran: 2017-08-31 06:20:28

1
5 4
#..#
#.##
#..#
#..#
####
valid

stark_attack: 2017-08-15 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.


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