Connection Status:
Competition Arena > RainyRoad

RainyRoad

SRM 525 · 2011-05-25 · by ir5

SRM 525 · 2011-05-25 · by ir5 · Simple Search, Iteration
Class Name: RainyRoad
Return Type: String
Method Name: isReachable
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Fox Ciel is going to take a path to meet her friends. The path is tiled with 1x1 square tiles. It is N tiles long and 2 tiles wide. If we imagine that the path is going from the left to the right, we can view it as a rectangle with 2 rows and N columns of tiles. The rows of the path are numbered 0 to 1 from top to bottom, and the columns of the path are numbered 0 to N-1 from left to right. Ciel starts at the tile in row 0, column 0. She has to reach the tile in row 0, column N-1.

In each step, Ciel can move to an adjacent tile. Two tiles are adjacent if they share at least one point (a side or a corner).

Because it rained yesterday, some tiles are covered by puddles of water. Ciel will not step on these tiles. You are given a String[] road. The j-th character of i-th element is 'W' if a tile at i-th row of j-th column is covered by water, and '.' otherwise.

Return the String "YES" if she can move to her destination without entering a tile which is filled with water. Otherwise, return "NO".

Notes

  • The constraints guarantee that the starting tile and the destination tile are never covered by water.

Constraints

  • road will contain exactly 2 elements.
  • Each elements of road will contain between 2 and 50 characters, inclusive.
  • All elements of road will contain the same number of characters.
  • Each character of road will be either '.' or 'W'.
  • The first character and the last character of 0-th element of road will be '.'.
Examples
0)
{".W.."
,"...."}
Returns: "YES"

One of the possible ways is as follows. Here, 'F' is the tile occupied by Fox Ciel. "FW.." "...." ".W.." "F..." ".W.." ".F.." ".W.." "..F." ".W.F" "...."

1)
{".W.."
,"..W."}
Returns: "YES"
2)
{".W..W.."
,"...WWW."}
Returns: "NO"
3)
{".."
,"WW"}
Returns: "YES"
4)
{".WWWW."
,"WWWWWW"}
Returns: "NO"

Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RainyRoad with a public method string isReachable(vector<string> road) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous