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 Setter:

MD. Jalal Uddin

Please login to submit solution to this problem.

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

Problem Stats

53/131

Solve/Submission

Ranking

# User Language Timing
01 feodorv C 0.00s
02 khmahbub20 C 0.00s
03 mir003 Cpp14 0.00s
04 seyedssz Cpp14 0.01s
05 Morass Cpp14 0.01s
06 rayhan50001 Cpp14 0.01s
07 dip_BRUR Cpp14 0.01s
08 MAHRahat Cpp14 0.01s
09 subhashis_cse Cpp14 0.01s
10 rajdipsaha Cpp14 0.02s
11 emrul Cpp14 0.02s
12 prantacse14 Cpp14 0.02s
13 anik_JU Cpp14 0.02s
14 bu_hridoy Cpp 0.02s
15 mahbub07 Cpp14 0.02s
16 Ehsanul_Fahad Cpp 0.02s
17 ProMAGFAT Cpp14 0.02s
18 nazmul_bzs Cpp14 0.02s
19 lightlessShadO Cpp14 0.02s
20 Bruteforcekid Cpp 0.03s
21 isakib Cpp 0.03s
22 adil_reza Cpp14 0.03s
23 Salty_Coder Cpp14 0.03s
24 pulak_ict_mbstu Cpp14 0.03s
25 Tamim028 Cpp 0.03s
26 SbrTa Cpp14 0.03s
27 Jubayer_Hasan Cpp14 0.03s
28 Aman_khan Cpp14 0.04s
29 bishal_biswas Cpp14 0.04s
30 Najat Cpp14 0.09s
31 Dinar Cpp14 0.09s
32 jalal Cpp14 0.24s
33 rashedul007 CSharp 0.37s
34 froghramar Cpp14 0.40s
35 Alim14 Cpp14 0.41s
36 tariqiitju Cpp14 0.41s
37 hasanbgc Cpp14 0.42s
38 arif2603 Cpp14 0.43s
39 sunkuet02 Cpp14 0.43s
40 RandyWaterhouse Python3 0.47s
41 sajal_khan Cpp14 0.49s
42 anowar1112 Cpp14 0.50s
43 KNUTH Cpp14 0.51s
44 murad_al_wajed Cpp14 0.52s
45 njrafi Cpp14 0.56s
46 Ishrak Cpp14 0.60s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support