Description
For thousands of years, salesmen have faced the problem of touring sites for potential customers, visiting each site exactly once, and minimizing the total cost of this tour. In the old days, these sites were towns spread out throughout the country, and the salesman had to travel the rickety, crooked roads that connected the towns. But now, in 2030, cities and have modernized and grown, so a salesman typically stays within the same city. Furthermore, modern cities are laid out in a grid-like pattern of tall skyscrapers, with sky bridges joining some pairs of adjacent skyscrapers on all floors.
The salesman has determined which floor of each skyscraper contains the most potential customers and will only visit the best floor of each skyscraper. Now the salesman must plan his course. Starting on the ground floor (floor 0) of the skyscraper in the northwest corner of the grid, the salesman must visit the specified best floor of each skyscraper before returning to the ground floor of either of the skyscrapers at the southwest, southeast, or northeast corners. In order to travel between floor 10 of one skyscraper and floor 6 of an adjacent skyscraper, the salesman first takes the sky bridge across to floor 10 of the adjacent skyscraper and then takes an elevator down 4 floors. Of course, because the salesman’s time is precious, he wants to minimize the total number of floors he must travel by elevator. For example, if his tour involves traveling from floor 3 to 8 to 5 to 10, the number of floors traveled by elevator is (8 − 3) + (8 − 5) + (10 − 5) = 13.
To make the salesman’s life (and yours) more difficult, some sky bridges do not exist between two adjacent skyscrapers, and in that case, obviously the salesman cannot fly across the gap.
Because modern cities are much larger than the small towns that salesmen dealt with generations ago, our salesman needs a plan so that he does not lose his bearings and visit a skyscraper more than once (in which case he will get beaten by the people for pestering them so much) or less than once (in which case he might have lost profit). To that end, the salesman has decided to only consider tours similar to the one in the figure. The salesman starts at the northwest corner, and either goes south or east for any distance (as long as all sky bridges exist along that path). Then, he turns towards away from the edge of the city and travels to the adjacent skyscraper, and turns again, heading back opposite the initial direction. After any amount of zig-zagging, the salesman can choose to switch over to zig-zagging in the other orientation.
Given the floors of each skyscraper in the city that the salesman wishes to visit and which sky bridges do not exist, compute the minimum number of floors that the salesman must travel on a tour that meets the above criteria. Also, print out the number of possible tours achieving that minimum.
Input
The first line contains two numbers M (1 ≤ M ≤ 1000) and N (1 ≤ N ≤ 1000), the dimensions of the city. Each of the next M lines contains N integers in the range [0, 100]. Each integer is the floor that the salesman must visit. Optionally following each integer might be a token specifying that some sky bridges do not exist. Suppose you just read the floor for location (x, y) (note that (0, 0) is the northwest corner, (N − 1, 0) is the northeast corner, (0, M − 1) is the southwest corner, and (N − 1, M − 1) is the southeast). If the token is x, no sky bridges exist between (x, y) and (x + 1, y). If the token is y, no sky bridges exist between (x, y) and (x, y + 1). All tokens and integers are separated by a single space.
Output
If there is no tour, print No solution. Otherwise, print out the number of tours and the minimum number of floors travelled.
Sample Input
2 4
0 y 10 20 30
5 8 25 28
Sample Output
1 tours, traveling a minimum of 60 total floors
http://poj.org/problem?id=2929
