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
Vipul Pandey: 2014-02-04 21:53:35

take input character by character using cin or getchar as there are spaces in the input. costed me WA.

Last edit: 2014-02-04 21:54:02
Rishav Goyal: 2014-02-03 12:35:30

Awesome fun at WA ;)

P_Quantum: 2014-01-19 07:04:47

easy one..!!

The Joker: 2013-12-12 23:21:48

can someone give some tricky test cases plz...
getting WA dont knw why... :(
submission id 10092196

BLANKRK: 2013-12-12 23:21:48

enjoyed solving this.... :)

sobhan: 2013-12-12 23:21:48

plz give me input :)

shiva_hellgeek: 2013-12-12 23:21:48

the problem is really nice.
but i don't know why a space is given between the characters whereas actually there is no space...

mudiyala: 2013-12-12 23:21:48

Loved solving it ~~!!! :D Wonderful testcases :)

Kumar Mrinal: 2013-12-12 23:21:48

piece of cake :D

god_father: 2013-12-12 23:21:48

easy one ;got Ac in first Attempt..


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