|
Алхимия
(Время: 1 сек. Память: 16 Мб Сложность: 42%)
Фактически, данная задача представляет собой классическую задачу на поиск наикратчайшего пути в в ориентированном невзвешанном графе. В качестве вершин здесь выступают химические вещества, а в качестве ребер – поцесс (возможность) получения одного вещества из другого. В силу небольших ограничений на количество вершин здесь применим любой алгоритм (кроме поиска в глубину) от поиска в ширину до алгоритма Флойда.
Пожалуй, наибольшую сложность в задаче представляет процесс формализации данных от строковых наименований химических веществ к обычному числовому представлению. Для этого следует провести нумерацию описанных во входных данных веществ и далее обращаться к ним по номерам. Для этого определим некоторую функцию GetID(name), которая по названию вещества name будет возвращать его номер. Наименования веществ будем хранить в некотором массиве p, причем название вещества c номером k будет храниться в p[k]. Используем пееменную n для хранения общего количества веществ. Функция GetID будет не только возвращать номер вещества, но и добавлять его в массив p, если ранее такого вещества не было. Данную функцию можно описать следующим образом:
int GetID(name){
for i=0..n-1
if(p[i]==s) return i
p[n]=s
return n++
}
В процессе чтения данных определим матрицу смежности a[i][j], где в a[i][j] будет 1, если возможно из вещества с номером i получить вещество с номером j, в противном случае a[i][j] будет равно 0. Заметим, что процесс формирования данной матрицы возможно совместно с чтением данных и заполнением массива p. Сам весь этот процесс можно представить следующим алгоритмом:
read(m)
a={0,…,0}
for i=1..m{
read(src, s, dest)
a[GetID(src)][GetID(dest)]=1
}
Read(src, dest)
После мы в переменных src и dest будем иметь названия исходного и получаемого веществ, а в массиве a – матрицу смежности. Применим волновой алгортим (поиск в ширину) для нахождения ответа на поставленную задачу. Используем некоторый массив d, где в d[k] будем хранить количество шагов, необходимых для получения вещества с номером k из исходного. Пока решение не найдено, будем там хранить нулевое значение. Для удобства будем хранить в d[k] значение, превышающее на единицу требуемое значение количества шагов. Так, первоначально обнулим массив, а d[start] положим равным 1 (здесь start=GetID(src)). Далее, присвоим всем d[j] значение 2, если a[start][j]=1. Это будет означать, что все такие вещества с номером j можно получить за одну реакцию. Далее всем d[j] присвоим 3, где для некоторого i a[i][j]=1 и d[i]=2. Так найдем все вершины, которые возможно достичь за 2 шага и т.д., на k-м шаге будем помечать вершины значением k+1, в которые можно достичь за k шагов. За n-1 таких действий мы заполним массив d, а ответом на задачу будет значение d[GetID(dest)]-1. Вышеописанный механизм заполнения массива d может быть представлен следующим образом:
d[GetID(src)]=1
for k=1..n-1
for i=0..n-1
if(d[i]==k)
for j=0..n-1
if(a[i][j]==1 and d[j]==0) d[j]=k+1
| |
