# DCP-3: Maze Tester Back to All Problems

Easy Graph Theory > Breadth First Search/Depth First Search

We are developing a game where player has to cross a maze to reach his/her destination. If he/she can reach destination then he/she will win that maze. There will be many mazes that user can conquer one by one. We are using a maze generator engine to generate these mazes. The engine generates a random maze in every stage. But the problem is, some of these random mazes can be invalid as there may not be any path for the player to reach the destination. Players will get annoyed if they receive such an invalid maze in the game so we want to discard such invalid maze and generate only valid mazes. To achieve this, we need to write a maze tester that can test a randomly generated maze and can tell whether it is valid maze or not. Let’s see whether you can help us or not. Input: ------ Input will consist of many mazes. Each maze will be **30x30** in dimension. Each **‘.’** Indicates a valid step for the player and each **‘X’** indicates an obstacle. **‘P’** is the starting position of the player and ‘G’ is the destination of the player. Boundary of the maze is marked with either **‘|’** or **‘-‘**. These boundaries are also unreachable and invalid for movement. Player can only move in 4 directions, up, down, left and right. It can’t move diagonally. Input is terminated by End of File. Output: ------- If the maze is valid then print **“Possible”** (without quotation) and if the maze is invalid then print **“Impossible”** (without quotation) in a separate line for each maze. Sample Input ------------ ------------------------------ |............................| |............................| |............................| |............................| |............................| |............................| |...........P................| |............................| |............................| |............................| |XXXXXXXXXXXX................| |...........XXXXXXXXXXXXXXXX.| |......................X.....| |......................XXX.XX| |............................| |............................| |............................| |............................| |............................| |............................| |............................| |............................| |............................| |............................| |......G.....................| |............................| |............................| |............................| ------------------------------ ------------------------------ |............................| |............................| |............................| |............................| |............................| |............................| |........X...................| |........X...................| |........X...................| |........X...................| |........X...................| |........XXXXXX..............| |...............XXXX.........| |..XXXXXXXXX....X..X.........| |..X.......X.G..X..X.........| |..X..XXXX.X....X..X.........| |..X.....X.XXXXXX..X.........| |..X...P.X.........X.........| |..XXXXXXX.........X.........| |..................X.........| |............................| |............................| |............................| |............................| |............................| |............................| |............................| |............................| ------------------------------ ------------------------------ |...X......................XP| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.XXXXXXXXXXXXXXXXXXXXXXXX.| |.X..........................| |.XXXXXXXXXXXXXXXXXXXXXXXXXX.| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |GX..........................| ------------------------------ ------------------------------ |.X.X......................XP| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.X......................X.| |.X.XXXXXXXXXXXXXXXXXXXXXXXX.| |.X..........................| |.XXXXXXXXXXXXXXXXXXXXXXXXXX.| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |.X..........................| |GX..........................| ------------------------------ Sample Output ------------- Possible Possible Possible Impossible

### Problem Limits

 Language Time Limit (seconds) C 1.00 C++ 1.00 C++14 1.00 C# 2.00 Go 2.00 Java 2.00 JavaScript 2.00 Objective-C 2.00 Perl 2.00 PHP 2.00 Python 2.00 Python3 2.00 Ruby 2.00 VB.Net 2.00

# 80/195

Solve/Submission

### Ranking

# User Language Timing
01 feodorv C 0.00s
02 mir003 Cpp14 0.00s
03 khmahbub20 C 0.00s
04 Robbinb1993 Cpp 0.00s
05 Phenomenal_1_Riad Cpp 0.00s
06 seyedssz Cpp14 0.01s
07 Morass Cpp14 0.01s
08 mahade31 Cpp14 0.01s
09 twyu0721 Cpp 0.01s
10 MRoy Cpp 0.01s
11 MAHRahat Cpp14 0.01s
12 traveller42 Cpp 0.01s
13 Jisancse Cpp 0.01s
14 subhashis_cse Cpp14 0.01s
15 rayhan50001 Cpp14 0.01s
16 dip_BRUR Cpp14 0.01s
17 mahbub07 Cpp14 0.02s
18 prantacse14 Cpp14 0.02s
19 emrul Cpp14 0.02s
20 rajdipsaha Cpp14 0.02s
21 shuvo_mbstu Cpp 0.02s
22 smsaleque Cpp14 0.02s
23 Ehsanul_Fahad Cpp 0.02s
24 SakibAlamin Cpp 0.02s
25 nazmul_bzs Cpp14 0.02s
26 _dipu Cpp14 0.02s
27 bu_hridoy Cpp 0.02s
28 hrOarr Cpp14 0.02s
29 anik_JU Cpp14 0.02s
30 Salty_Coder Cpp14 0.03s
31 Tamim028 Cpp 0.03s
32 pulak_ict_mbstu Cpp14 0.03s
33 adil_reza Cpp14 0.03s
34 asfak Cpp 0.03s
35 Bruteforcekid Cpp 0.03s
36 isakib Cpp 0.03s
37 Jubayer_Hasan Cpp14 0.03s
38 SbrTa Cpp14 0.03s
39 prateepm Cpp14 0.03s
40 muntasir10mu Cpp 0.03s
41 Aman_khan Cpp14 0.04s
42 Logic_Hunter Cpp14 0.04s
43 sabertooth Cpp 0.04s
44 bishal_biswas Cpp14 0.04s
45 Najat Cpp14 0.09s
46 Dinar Cpp14 0.09s
47 Tanmoy Cpp14 0.24s
48 jalal Cpp14 0.24s
49 Partha11 Cpp 0.26s
50 aiven Python3 0.32s
Feedback