# 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/C++ 1.00 Java 2.00 C# 2.00 PHP 2.00

# 29/78

Solve/Submission

### Ranking

# User Language Timing
01 mahrahat Cpp 0.01s
02 seyedssz Cpp 0.01s
03 rayhan50001 Cpp 0.01s
04 subhashis_cse Cpp 0.01s
05 rajdipsaha Cpp 0.02s
06 ProMAGFAT Cpp 0.02s
07 mahbub07 Cpp 0.02s
09 Jubayer_Hasan Cpp 0.03s
10 Salty_Coder Cpp 0.03s
11 Aman_khan Cpp 0.04s
12 Najat Cpp 0.09s
13 Dinar Cpp 0.09s
14 jalal Cpp 0.24s
15 froghramar Cpp 0.40s
16 Alim14 Cpp 0.41s
17 tariqiitju Cpp 0.41s
18 hasanbgc Cpp 0.42s
19 sunkuet02 Cpp 0.43s
20 arif2603 Cpp 0.43s
21 sajal_khan Cpp 0.49s
22 anowar1112 Cpp 0.50s
23 KNUTH Cpp 0.51s