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

82/637

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 dip_BRUR Cpp14 1.39s
10 _dipu Cpp14 1.41s
11 shahadat191 Cpp14 1.41s
12 i_love_nikita_gautam Cpp14 1.43s
13 Riaz_BSMRSTU Cpp 1.46s
14 CrazyMerlyn Cpp14 1.51s
15 Peregrine_Falcon Cpp 1.51s
16 notorious_94 Cpp 1.52s
17 Robbinb1993 Cpp14 1.53s
18 SoSooding Cpp14 1.54s
19 ak281999 Cpp 1.54s
20 vatsalsharma376 Cpp14 1.57s
21 Nirjhor Cpp14 1.58s
22 ssavi Cpp14 1.59s
23 arsho Cpp14 1.62s
24 S_A_Babaei Cpp 1.64s
25 Durbin Cpp14 1.67s
26 alif_biswas Cpp 1.70s
27 racsosabe Cpp 1.71s
28 KIRIN_36 Cpp14 1.73s
29 nafiz0080 Cpp14 1.76s
30 math10 Cpp14 1.80s
31 swarmonster Cpp14 1.85s
32 humbletheif Cpp14 1.87s
33 pulak_ict_mbstu Cpp 1.94s
34 sajib_kumar_biswas Cpp 1.99s
35 ehsan_sshuvo96 Cpp 2.02s
36 ShihabHossain Cpp14 2.05s
37 mamun4122 Cpp14 2.10s
38 sabertooth Cpp 2.23s
39 swapnil Cpp14 2.25s
40 diego_v1 Cpp14 2.31s
41 prateepm Cpp14 2.41s
42 seyedssz Cpp14 2.43s
43 Mahmudul_Tushar Cpp14 2.44s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support