Description

ROR game is a game where players are divided into two teams and a team wins if they destroy camp of the other team first. Therefore, each team should go to other team's camp as quickly as possible.

From now on, you are going to play the game as member of one side. Following shows an example where in 5 x 5 map, your character is placed in (row: 1, column: 1) and camp of the other team is placed in (row: 5, column: 5).

최단거리1_sxuruo.png

In the above figure, you cannot move to the black space because it is surrounded by wall whereas white space is opened. The character moves by one space at once in East, West, South, and North direction. Also the character cannot go out of the map.
Following example shows 2 ways to move the character to the other team's camp.

  • In the first method, the character arrives at the camp of the other team through 11 spaces.

최단거리2_hnjd3b.png

  • In the second method, the character arrives at the camp of the other team through 15 spaces.

최단거리3_ntxygd.png

Since in the above example, there is no way to move to the other team's camp more quickly than the first method, it is the fastest way to reach the camp of the other team.

If the other team builds wall around the camp, you may not move to their camp. For example, in the following case, your character cannot arrive at the other team's camp.

최단거리4_of9xfg.png

Given the status of game map maps as parameter, write a function "solution" to return the minimum number of spaces required for your character to arrive at the camp of the other team. But, return -1 when there is no way to reach their camp.

Constraints
  • maps is a 2-dimensional array containing the status of the game map with "n" x "m" size. "n" and "m" are natural number between 1 and 100.
  • "n" and "m" may be either the same or different each other, but there is no case where both are given as 1.
  • "maps" consists of 0 and 1 only, which indicates the space with wall and without wall, respectively.
  • Initially, the character is located at the left top of the game map (1, 1), and the camp of the other team is at the right bottom of the game map ("n", "m").

Examples
maps answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1

Example #1
Data is given as follows.

최단거리6_lgjvrb.png

The shortest path to move your character to the other team's camp is as follows.

최단거리2_hnjd3b (1).png

Therefore, since the character passes through total 11 spaces, return 11.

Example #2
It is the same with an example in the problem statement where there is no way to reach the camp of the other team. Hence return -1.

Result Stop
Result of [Run] or [Submit] will be displayed here