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
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

jarvis: 2015-10-24 12:16:39

Detained from class tests :P :P AC :D here!

hardik agrawal: 2015-10-23 13:47:36

first bfs! nice problem... my 101st.. :)

sri: 2015-09-11 09:22:10

####
#...
#.##
#.##
is this valid or not?
how?


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