A Tour of Odesa Restaurants
Odesa is a renowned city, often referred to as Odesa-mama, as it has become a welcoming home for people from diverse nationalities. Importantly, these individuals coexist peacefully, embracing different cultures, perspectives, and languages. As a result, Odesa boasts a variety of restaurants offering cuisines from around the world.
Tourists, known for their love of food, enjoy sampling different national dishes, from Georgian to French and Italian. However, moving between these restaurants can be time-consuming. As a resourceful programmer, you aim to streamline this process. With a map of Odesa's restaurants at your disposal, you're ready to optimize your culinary journey.
Nationalities are labeled from 1 to K. Each restaurant on the map is identified by the nationality it represents. Your goal is to visit these cuisines in numerical order (1, 2, 3, etc.), visiting each nationality's cuisine exactly once. You can begin at any restaurant of the first cuisine and conclude at any restaurant of the K-th cuisine. Your task is to determine the shortest path that fulfills these criteria.
In Odesa, streets are famously perpendicular (or so the tour guides say :)), allowing us to model the map as a rectangle N×M, divided into unit squares. Movement is allowed between adjacent squares sharing a side. The distance between two cells with coordinates (x_1, y_1) and (x_2, y_2) is calculated as |x_2-x_1|+|y_2-y_1|. Note that you can pass through a square containing a restaurant without stopping there.
Input
The first line contains the integers N, M, K (1 ≤ N, M ≤ 100, 1 ≤ K ≤ N×M). The following N lines each contain M numbers, indicating the nationality number (from 1 to K) of the restaurant in that unit square, or 0 if there is no restaurant there. It is guaranteed that restaurants representing all K nationalities are present on the map.
Output
Output a single number, representing the length of the shortest path.