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
ravi teja: 2013-12-12 23:21:48

plz check submission id: 839598
checked for given as well as lot of other test cases, giving WA

Aditya Pande: 2013-12-12 23:21:48

m getting WA for my submission
7361888 but i tried a lot of test cases myself and it gave the correct answer everytime
@cegprakash please tell me for which tricky case does my submission fail

gabber: 2013-12-12 23:21:48

is this valid?
1 2
..

cegprakash: Yes

Last edit: 2012-11-25 15:38:54
Sardar Khan: 2013-12-12 23:21:48

simple graph problem

npsabari: 2013-12-12 23:21:48

easy one!

Aradhya: 2013-12-12 23:21:48

goodness me :D in input there is a apace btw two characters.. but actually it is nt so.. got too many wrng answers for that misconception.. be careful :D

Simón Murillo Gómez: 2013-12-12 23:21:48

@himanshu jain is invalid
"A valid maze has exactly one entry point and exactly one exit point (EXACTLY 2 OPENINGS IN THE EDGES)"

himanshu jain: 2013-12-12 23:21:48

is this case a valid case?
4
5 5
##.##
##.#.
#..##
#.###
#.###
i have 3 openings , but one cannot be used as entry/exit

vishal chaudhary: 2013-12-12 23:21:48

i m getting SIGSEGV error , my code id is 7485646 ...plz help..:(

Swapnil R.Mehta: 2013-12-12 23:21:48

Got AC!

Last edit: 2012-08-16 10:19:45

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