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

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

hide comments
2024-09-15 17:25:06
It's been the edited version of my question. I don't need any help with this task anymore. Finally, I was able to fix it and my solution passed.

Last edit: 2024-09-16 23:39:21
2021-12-01 18:58:52
AC in 2nd time
2020-12-26 17:50:09
AC in one go....;)
2020-10-03 19:38:29
pqv907 the test case you provied will output invalid
2020-08-13 18:39:34
What am I doing wrong? Like most of the users I'm also getting WA on 5th testcase.
My approach:
1: count all the entry/exit points if it is more than 2 -> invalid
else
call bfs with one of those points and see if other point can be reached.

any suggestions?
2020-05-30 20:36:20 i'm awesome :D
My 150th :D
2020-05-25 08:15:45
If you get WA at 5th TC.
Try
1
3 1
###

or
1
1 3
#
#
#
2020-04-27 23:51:26
AC in one go!!!
2020-01-21 09:48:25
1 shot ac
2019-12-12 12:52:58
Read the question carefully. Everything is explained there.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.