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
AJEET KUMAR: 2015-08-09 21:00:04

constraint for m and n in question is not valid. take your array size much greater for example 1000.

viraj: 2015-06-06 17:57:40

Pay special attention to "(exactly 2 openings in the edges)".

Usama: 2015-04-28 14:28:47

what are the answer of these

.#.
.##

and

#...#

?

Last edit: 2015-04-28 14:32:12
Subrat Singh: 2015-02-26 15:04:16

finally done :)

Last edit: 2015-02-27 15:29:33
Malfple: 2014-12-15 13:13:03

I don't get it...Checked overbound already~~WA. Used another absurd checking~~AC

Girish Rathi: 2014-09-09 13:39:08

easy one with simple solution

Mitch Schwartz: 2014-07-10 17:17:20

@sudharshan G: your brain.

sudharshan G: 2014-07-10 17:01:07

where i get this code please help

|RAMSDEN|: 2014-06-27 09:27:46

many WAs due to silly mistake
:p wasn't clearing queue at every iteration..
input format is same as mentioned:)

Master_Mind: 2014-06-14 09:02:12

plzz provide some tricky cases.
any reasons for wa.


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