You just qualified for a programming contest which is held in a very far city. Since your family loves you too much, they decided to come along with you. Of course, your little brother will come also.
You will drive from your home city to the city where the contest is being held, possibly stopping at several other cities along the way. The time it takes to get from one city to the next is called an interval. If an interval of your trip is ever longer than the previous interval, your brother will start crying and your parents will have to turn the car around and go back home, forcing you to miss the contest. Therefore, you must plan the trip so that doesn't happen. If there are multiple ways to achieve this, you must choose the one that minimizes the total length of the trip.
You will be given a String[] **graph** containing the distances between the cities where you may stop. The *j*th character of the *i*th element of **graph** is the distance from the *i*th city to the *j*th city. If it's '0' (zero), it means that you cannot go directly from the ith city to the jth city. Characters 'a' to 'z' represent distances of 1 to 26, and characters 'A' to 'Z' represent distances of 27 to 52. You live in city 0 and the contest is being held in city 1. Return the length of the shortest route from city 0 to city 1 that will not make your brother cry. If no such route exists, return -1. |