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
i'm awesome :D: 2020-05-30 20:36:20

My 150th :D

pqv907: 2020-05-25 08:15:45

If you get WA at 5th TC.
Try
1
3 1
###

or
1
1 3
#
#
#

upen3103: 2020-04-27 23:51:26

AC in one go!!!

dkkv0000: 2020-01-21 09:48:25

1 shot ac

b1nary_: 2019-12-12 12:52:58

Read the question carefully. Everything is explained there.

meoconxinhxan: 2019-10-11 03:49:15

Why Map :
3 4
#..#
#.##
#.##
is invalid pls help me

Reply: Because there are 3 openings

Last edit: 2019-11-04 13:16:24
aj_254: 2019-05-11 13:06:38

ac in second go easy one. solvable in python

ilham_sr0611: 2019-04-19 14:14:48

Last edit: 2019-04-19 14:15:15
ayushr2: 2018-09-27 22:07:12

How do you see what TCs you pass?

nitish235: 2018-08-26 08:55:32

if you sol is failing for tc 5
try this
1
2 3
.##
.##


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