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
abhishek181297: 2017-03-15 04:43:26

AC in 1 go . used backtracking.
Thanks @s1234 for the hint . Key point ...
More than two opening even if they are not connected will cause invalid:
##.#
.#.#
##.#
##.# is invalid.

Last edit: 2017-03-15 04:44:56
gboduljak: 2017-02-27 15:30:07

can be solved with backtracking

cegprakash: 2016-10-21 15:05:18

vandan1177 : invalid

vandan1177: 2016-10-16 13:19:21

Is "....." valid or invalid?

madhavgaba: 2016-10-04 22:25:04

finally understood [spoiler] ^_^ credits @pulkitgulati

Last edit: 2016-10-21 15:05:55
nguyenkhieu: 2016-09-21 15:05:09

đm ez vcl các bạn ei

prakash: 2016-09-13 23:58:19

After lot of silly mistakes got it!

s1234: 2016-07-23 03:29:53

More than two opening even if they are not connected will cause invalid:
##.#
.#.#
##.#
##.# is invalid.

rushikesh: 2016-07-07 05:25:20

17238184 my code id . please can someone tell me what is wrong with my code it hits me with SIGSEGV error

fadi_yns: 2016-06-22 07:28:40

sir, its valid cause you have exactly one entry point and exactly one exit point and there is a path between this tow points


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