LCC '22 Contest 3 J3 - Roller Coaster

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

A group of computer science students are going to the amusement park!

Because they do not like going outside, the amusement park is an indoor building with a height of M.

The students see a very scary looking roller coaster, but scary is fun, right?! They draw the roller coaster on an N by M celled grid paper, with cell (1, 1) being on the bottom-left and cell (N, M) on the top-right.

Each column will contain exactly one / or \ track, with the rest being empty space as denoted by .. (1, 1) and (N, 1) are guaranteed to contain the track for their respective columns.

The roller coaster is safe if one can follow the coaster's path from (1, 1), the start of the coaster, to the end at (N, 1) without any jumps. No jump occurs if:

  • the track on a column is /, the track on the next column is \ and are on the same row. For example,
....
./\.
....
  • the track on a column is \, the track on the next column is / and are on the same row. For example,
....
.\/.
....
  • the track on a column is /, the track on the next column is / and is one row above. For example,
....
../.
./..
  • the track on a column is \, the track on the next column is \ and is one row below. For example,
....
.\..
..\.

Otherwise, there is a jump and the coaster is unsafe. Can you determine whether the coaster is safe or not?

Constraints

2 \le N, M \le 10^3

Each cell will either be ., /, or \.

Each column will contain exactly one \ or / characters.

Cell (1, 1) will be / and cell (N, 1) will be \.

Input Specification

The first line will contain 2 space-separated integers N and M.

The next M lines will contain N characters denoting the drawing of the roller coaster for that row.

Output Specification

According to the rules above, output safe if the roller coaster is safe and unsafe otherwise.

Sample Input 1

10 5
..........
...../\...
../\/..\..
./......\.
/........\

Sample Output 1

safe

Sample Input 2

6 4
.../..
../...
./..\.
/....\

Sample Output 2

unsafe

Comments

There are no comments at the moment.