DCP-60: Holloween Party Back to All Problems

Hard Graph Theory > Breadth First Search/Depth First Search


Festive season is going on in the city of “Kam kaj nai” . Though most of the people in the city of kam kaj nai aren’t serious about their work and their main motivation of living is do a party in every day . Torongo being most sincere person in the city of “kam kaj nai” never wants to take day off for this unnecessary parties . But he is also very kind never wants to hard anyone of the city of “kam kaj nai” . Torongo’s house located at cell ( 0 , 0 ) in the gird wise representation of city of “kam kaj nai” and his office located at cell( n – 1 , m – 1 ) . Inorder to go on cell to another cell torongo needs to visit one of 4 adjacent cell ( Right , Left , Up , Down ) from is current cell . Today people of the city “kam kaj nai” celebrating Holloween party in their house so there is a dress code to attain the party . If currently torongo at ( x1 , y1 ) position and his next destination is ( x2 , y2 ) position then 1. If DressCode( x1 , y1 ) == DressCode( x2 , y2 ) torongo can go to ( x2 , y2 ) position without changing his dress. 2. If DressCode( x1 , y1 ) != DressCode( x2 , y2 ) torongo can’t go to ( x2 , y2 ) position without changing his dress. In this problem you need to minimum number of dress torongo need to change to go his office ( n – 1 , m – 1 ) ( where n is row number and m is column number ) from his house ( 0 , 0 ) . Input: ------ The first line consists of an integer **t ( t <= 15 )** , the number of test cases. For each test case, the first line consists of two integers n and m **( 1 <= n , m <= 1000 )** representing the order of the rectangular city of **“kam kaj nai”** followed by R strings representing the map of the rectangular city of **“kam kaj nai”** . Output: ------- For each test case, print a line **“Case x: y”** where x is replaced by the test case number and y minimum number of times torongo need to change his dress . Sample Input ------------ 2 2 2 11 11 2 3 123 456 Sample Output ------------- Case 1: 0 Case 2: 3


Problem Setter:

Shakil Ahmed

Please login to submit solution to this problem.

Problem Limits

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

Problem Stats

93/814

Solve/Submission

Ranking

# User Language Timing
01 tariqiitju Cpp14 0.00s
02 feodorv C 0.77s
03 Morass Cpp14 1.12s
04 Sarwar05 Cpp 1.18s
05 ajkdrag Cpp 1.19s
06 a_rahman Cpp 1.23s
07 Reayz Cpp 1.23s
08 BungakuShoujo Cpp14 1.32s
09 aboAdnan Cpp 1.32s
10 dip_BRUR Cpp14 1.39s
11 _dipu Cpp14 1.41s
12 shahadat191 Cpp14 1.41s
13 i_love_nikita_gautam Cpp14 1.43s
14 SAIF_IIT8_JU Cpp 1.45s
15 Riaz_BSMRSTU Cpp 1.46s
16 CrazyMerlyn Cpp14 1.51s
17 Peregrine_Falcon Cpp 1.51s
18 notorious_94 Cpp 1.52s
19 Robbinb1993 Cpp14 1.53s
20 SoSooding Cpp14 1.54s
21 ak281999 Cpp 1.54s
22 _mHm_ Cpp 1.56s
23 vatsalsharma376 Cpp14 1.57s
24 Nirjhor Cpp14 1.58s
25 ssavi Cpp14 1.59s
26 arsho Cpp14 1.62s
27 S_A_Babaei Cpp 1.64s
28 Durbin Cpp14 1.67s
29 alif_biswas Cpp 1.70s
30 racsosabe Cpp 1.71s
31 sajibreadd Cpp14 1.71s
32 KIRIN_36 Cpp14 1.73s
33 nafiz0080 Cpp14 1.76s
34 math10 Cpp14 1.80s
35 swarmonster Cpp14 1.85s
36 humbletheif Cpp14 1.87s
37 abrunoaa Cpp14 1.88s
38 tymefighter Cpp14 1.92s
39 pulak_ict_mbstu Cpp 1.94s
40 sajib_kumar_biswas Cpp 1.99s
41 ehsan_sshuvo96 Cpp 2.02s
42 ShihabHossain Cpp14 2.05s
43 mamun4122 Cpp14 2.10s
44 sabertooth Cpp 2.23s
45 swapnil Cpp14 2.25s
46 diego_v1 Cpp14 2.31s
47 Mushfiqur_Rahman Cpp14 2.31s
48 prateepm Cpp14 2.41s
49 seyedssz Cpp14 2.43s
50 Mahmudul_Tushar Cpp14 2.44s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support