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
longthtran: 2017-08-31 06:20:28

1
5 4
#..#
#.##
#..#
#..#
####
valid

stark_attack: 2017-08-15 12:48:51

getting WA on the 5th test case. plz, provide any tricky test case. I have gone through all corner cases but still unable to pass through.

yara_farid: 2017-08-03 22:00:51

.

Last edit: 2017-08-07 10:31:15
gopikrishna_p: 2017-06-18 20:59:23

good problem to try :) [spoiler] figure out base cases ac in 5 th go :)

Last edit: 2017-08-02 13:07:16
candide: 2017-04-12 20:59:56

The problem is well settled and the description is clear although the question being academic. The problem receives a [big spoiler sentence] (i implemented both for comparison purpose).

Last edit: 2017-08-02 13:08:15
anurag_tangri: 2017-03-15 21:24:27

AC :) Just apply [spoiler]

Last edit: 2017-03-22 18:44:46
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?


Added by:cegprakash
Date:2012-05-11
Time limit:0.824s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU