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

@Prabhat:

.##
.##
is a valid maze

winner: 2013-12-12 23:21:48


Last edit: 2012-07-29 08:41:44
♘Prabhat: 2013-12-12 23:21:48

what is answer of this
.##
.##

and if these mazes are
equivalent ________
.............# ________|

Last edit: 2012-07-29 08:45:51
Aditya Pande: 2013-12-12 23:21:48

Last edit: 2012-12-18 15:53:47
Zhouxing Shi: 2013-12-12 23:21:48

I got WA all the time,could you @pandian @cegprakash tell me why ? THANKS.

What does "in the corner" mean?

REPLY: sorry, it's actually edges

Last edit: 2012-07-26 10:47:20
Ehor Nechiporenko: 2013-12-12 23:21:48

Could you please answer 2 questions?
1) Is there whitespace between . and # characters in input?
2) Is corner point both entry and exit?

Abhishek Mishra: 2013-12-12 23:21:48

very nyc question

Last edit: 2012-06-20 18:33:56
Pandian: 2013-12-12 23:21:48

@Nnavneetsinha : You can't move from one '.' to another '.' with the possible moves up,down,left and right.
@Tjandra : the test cases are correct.

Last edit: 2012-06-01 03:41:50
(Tjandra Satria Gunawan)(曾毅昆): 2013-12-12 23:21:48

Is the test case ok? I'm getting WA

RAJDEEP GUPTA: 2013-12-12 23:21:48

what are the possible moves??
EDIT: up, down, left, right.

EDIT EDIT: hey specify that on the problem statement -_-

Last edit: 2012-11-18 20:14:47

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