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

76/601

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

Your feedback is our precious!



Or call +88 02 9853138 for support