[UVA] 11487 - Gathering Food
|
G |
Gathering Food
|
Winter is approaching! The weather is getting colder and days are becoming shorter. The animals take different measures to adjust themselves during this season.
- Some of them "migrate." This means they travel to other places where the weather is warmer.
-Few animals remain and stay active in the winter.
-Some animals "hibernate" for all of the winter. This is a very deep sleep. The animal's body temperature drops, and its heartbeat and breathing slow down. In the fall, these animals get ready for winter by eating extra food and storing it as body fat.
For this problem, we are interested in the 3rd example and we will be focusing on ‘Yogi Bear’.
Yogi Bear is in the middle of some forest. The forest can be modeled as a square grid of size N x N. Each cell of the grid consists of one of the following.
. an empty space
# an obstacle
[A-Z] an English alphabet
There will be at least 1 alphabet and all the letters in the grid will be distinct. If there are n letters, then it will be from the first n alphabets. Suppose n = 3, that means there will be exactly 1 A, 1 B and 1 C.
The letters actually represent foods lying on the ground. Yogi starts from position ‘A’ and sets off with a basket in the hope of collecting all other foods. Yogi can move to a cell if it shares an edge with the current one. For some superstitious reason, Yogi decides to collect all the foods in order. That is, he first collects A, then B, then C and so on until he reaches the food with the highest alphabet value. Another philosophy he follows is that if he lands on a particular food he must collect it.
Help Yogi to collect all the foods in minimum number of moves so that he can have a long sleep in the winter. You are also required to find the total number of shortest paths he can take that meets the above constraints.
Input
There will be several cases in the input file. Each case starts with, N(N<=10), the size of the grid. Each of the next N lines contains N characters each. Input ends with a value of 0 for N.
Output
For each case, output the case number first. If it’s impossible to collect all the foods, output ‘Impossible’. Otherwise, print the shortest distance followed by the total number of distinct paths. Since the total number of shortest paths can be very big, output the result modulo 20437.
Sample Input Output for Sample Input
|
5 |
Case
1: 15 1
|
Problem Setter : Sohel
Hafiz
Special Thanks : Md.
Arifuzzaman Arif
從地圖中依序收及食物，按照 'A', 'B', ... 'Z', 計算最少花費的總步數，以及在走法有多少種。
當食物還沒被拿起時，必須當成障礙物。
題目解法；
也就是相當於依序找到相鄰兩個最短路長度與方法，然後一個加總、另一個相乘。
#include <stdio.h>
#include <queue>
#include <algorithm>
#define mod 20437
using namespace std;
int n;
char g[20][20];
void sol() {
int i, j, k, m = 0;
int px[26], py[26];
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
if(g[i][j] >= 'A' && g[i][j] <= 'Z') {
px[g[i][j]-'A'] = i;
py[g[i][j]-'A'] = j;
m = max(m, g[i][j]-'A');
}
}
}
int len = 0, path = 1;
int x, y, tx, ty;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
g[px[0]][py[0]] = '.';
for(i = 0; i < m; i++) {
queue<int> X, Y;
int dist[20][20] = {}, dp[20][20] = {}, nt = i+1+'A';
X.push(px[i]), Y.push(py[i]);
dist[px[i]][py[i]] = 1;
dp[px[i]][py[i]] = 1;
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
for(int i = 0; i < 4; i++) {
tx = x+dx[i], ty = y+dy[i];
if(tx < 0 || ty < 0 || tx >= n || ty >= n)
continue;
if(g[tx][ty] != '.' && g[tx][ty] != nt)
continue;
if(dist[tx][ty] == 0) {
dist[tx][ty] = dist[x][y]+1;
X.push(tx), Y.push(ty);
}
if(dist[tx][ty] == dist[x][y]+1) {
dp[tx][ty] += dp[x][y];
dp[tx][ty] %= mod;
}
}
}
if(dist[px[i+1]][py[i+1]] == 0) {
puts("Impossible");
return;
}
len += dist[px[i+1]][py[i+1]]-1;
len %= mod;
path *= dp[px[i+1]][py[i+1]];
path %= mod;
g[px[i+1]][py[i+1]] = '.';
}
printf("%d %d\n", len, path);
}
int main() {
int cases = 0, i;
while(scanf("%d", &n) == 1 && n) {
for(i = 0; i < n; i++)
scanf("%s", g[i]);
printf("Case %d: ", ++cases);
sol();
}
return 0;
}