# 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 Limits

 Language Time Limit (seconds) C/C++ 2.50 Java 4.00 C# 4.00 PHP 4.00

# 23/148

Solve/Submission

### Ranking

# User Language Timing
01 ssavi Cpp 1.59s
02 arsho Cpp 1.62s
03 KIRIN_36 Cpp 1.73s
04 math10 Cpp 1.80s
05 nafiz0080 Cpp 1.82s
06 mamun4122 Cpp 2.10s
07 swapnil Cpp 2.25s
08 Mahmudul_Tushar Cpp 2.44s
Feedback