Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
BestIn
0 / 0 / 0
Регистрация: 16.05.2013
Сообщений: 10
#1

Задача для лабораторной - C++

24.05.2013, 19:19. Просмотров 368. Ответов 2
Метки нет (Все метки)

Помогите пожалуйста написать вот это,очень нужно!Буду очень благодарен.
Задача

Узнав, что лич Сандро ушёл воевать с королём демонов, эрафийские военачальники решили воспользоваться его отсутствием и захватить Тёмную крепость. Из Стедвика вышла армия крестоносцев во главе с Катериной Айронфист. В тот же день из лесов АвЛи им на помощь вышла армия эльфов-снайперов под предводительством легендарного стрелка Джелу. Военачальники прекрасно понимают, что пехота уязвима для личей, а стрелы эльфов крайне неэффективны против скелетов, поэтому двум армиям нужно объединиться и напасть на крепость одновременно. И поскольку Сандро может вернуться в любой момент, Тёмная крепость должна быть атакована как можно раньше. Вас же, как придворного картографа, попросили посчитать, какое минимальное количество дней уйдёт на реализацию этого плана.
Эрафия поделена на квадратные районы. Некоторые из них проходимы, некоторые — нет. За один день каждая армия может перейти в любой из 8 соседних (имеющих общую вершину) районов, если он проходим. В некоторых проходимых районах Эрафии установлен телепорт одного из 26 типов. Тип телепорта обозначается заглавной латинской буквой. Если армия располагается в районе с телепортом, то она может мгновенно переместиться в любой район с телепортом того же типа. В тот момент, когда обе армии оказываются в одном районе, они объединяются и далее перемещаются как единое целое. До объединения ни одна из армий не может нападать на крепость Сандро, то есть делать ход в район, в котором расположена крепость.


Исходные данные
В первой строке через пробел записаны числа n и m — размеры карты Эрафии (1 ≤ n, m ≤ 100). Далее задана сама карта — n строк по m символов в каждой. Символы имеют следующий смысл:
'#' — непроходимый район.
'.' — проходимый район.
'A'…'Z' — телепорт соответствующего типа.
'$' — армия Катерины.
'!' — армия Джелу.
'*' — крепость Сандро.
Гарантируется, что символы '*', '$', '!' встречаются на карте ровно один раз.

Результат
Выведите единственное число — минимальное количество дней, через которое объединённая армия сможет напасть на крепость Сандро. Если нападение совершить невозможно, выведите «Impossible».
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.05.2013, 19:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача для лабораторной (C++):

Помогите с лабораторной - C++
Задание Открыть файл, содержащий 10 целых чисел, показать их в диалоге, создать новый файл, записать в него среднее арифметическое этих...

Хэлп по лабораторной 2 - C++
Я прошу прощения, понимаю что выгляжу глупо, но не мог бы кто помочь с остальными 8 вопросами - не все зарегистрированы в контакте,...

Задание по лабораторной работе - C++
Вот такое задание. Не могу понять, как именно все это организовать. В голове только вариант "если др в интервале дд. мм-дд. мм, то знак...

Использовать программу, составленную при выполнении лабораторной работы №10 - C++
Использовать программу, составленную при выполнении лабораторной работы №10. #include <iostream> #include <stdio.h> #include...

Реальная задача для реального проекта для желающих покодить - C++
Привет:) Попросили сделать парсер сайта по-дружески, но у меня реально времени на него нет. Если кому-то интересно, могу двигать в...

Помогите!Задача для С - C++
Доброго времени суток=) Мне срочно нужен исходник, пожалуста помогите.

2
BestIn
0 / 0 / 0
Регистрация: 16.05.2013
Сообщений: 10
02.06.2013, 13:25  [ТС] #2
Вообщем вот такой код у меня получился,но не проходит 25 тест(на тимусе),не знаю что делать.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const int p=31;
const int maxn=1000000;
int n;
string s1,s2;
vector <int> hasht[maxn];
 vector <int> prefix1,prefix2;
vector <int> ps;
 
bool Comp_strs(string &s1,string &s2,int num1,int num2,int l)
{
 for (int i=num1,j=num2;i<num1+l;i++,j++)
 if (s1[i]!=s2[j]) return false;
 return true;
}
 
void Get_hash(int l)
{
 int tmp_hash;
 for (int i=0;i<=s1.length()-l;i++)
 {
 if (i) tmp_hash=prefix1[i+l-1]-prefix1[i-1];
 else tmp_hash=prefix1[i+l-1];
 if (tmp_hash<0) tmp_hash+=maxn;
 tmp_hash=(1ll*tmp_hash*ps[n-i])%maxn;
 hasht[tmp_hash].push_back(i);
 }
}
bool Check_hash(int l,int &beg_str)
{
 int tmp_hash;
 for (int i=0;i<=s2.length()-l;i++)
 {
 if (i) tmp_hash=prefix2[i+l-1]-prefix2[i-1];
 else tmp_hash=prefix2[i+l-1];
 if (tmp_hash<0) tmp_hash+=maxn;
 tmp_hash=(1ll*tmp_hash*ps[n-i])%maxn;
 for (int j=0;j<hasht[tmp_hash].size();j++)
 if (Comp_strs(s1,s2,hasht[tmp_hash][j],i,l))
 {
 beg_str=hasht[tmp_hash][j];
 return true;
 }
 }
 return false;
}
 
void Init_prefix()
{
 prefix1.resize(n);
 prefix2.resize(n);
 ps.resize(n+1);
 ps[0]=1;
 ps[1]=p;
 prefix1[0]=(s1[0]-'A'+1)%maxn;
 prefix2[0]=(s2[0]-'A'+1)%maxn;
 for (int i=1;i<n;i++)
 {
 prefix1[i]=(1ll*(s1[i]-'A'+1)*ps[i]+prefix1[i-1])%maxn;
 prefix2[i]=(1ll*(s2[i]-'A'+1)*ps[i]+prefix2[i-1])%maxn;
 ps[i+1]=(1ll*ps[i]*p)%maxn;
 }
}
 
void Clear()
{
 for (int i=0;i<maxn;i++)
 hasht[i].clear();
}
 
bool Check_in_strs(int l,int& beg_str)
{
 Clear();
 Get_hash(l);
 return Check_hash(l,beg_str);
}
 
 void Search()
{
 int l=0,r=n+1,m;
 int beg_str;
 while (r-l!=1)
 {
 m=(l+r)/2;
 if (Check_in_strs(m,beg_str)) l=m;
 else r=m;
 }
 if (l==0) cout << "";
 else 
 {
 Check_in_strs(r-1,beg_str);
 for (int i=beg_str;i<beg_str+r-1;i++)
 cout << s1[i];
 }
}
 
 
int main()
{
 //ifstream cin ("input.txt");
 cin >> n;
 cin >> s1 >> s2;
 Init_prefix();
 Search();
 return 0;
}
0
BestIn
0 / 0 / 0
Регистрация: 16.05.2013
Сообщений: 10
04.06.2013, 00:04  [ТС] #3
ПОМОГИТЕ!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.06.2013, 00:04
Привет! Вот еще темы с ответами:

Задача для уравнения теплопроводности - C++
Решить задачу на с++ для уравнения теплопроводности dU/dt = a2 * d2U/dx2, 0&lt;x&lt;l, t&gt;0 U(x,0) = U0(x) , 0=&lt;x=&lt;l dU/dx =...

Задача для проверки навыков - C++
Подскажите пару тройку заданий для &quot;разминки&quot;, что можно сделать, что-бы вспомнить весь синтаксис с++.

Задача по С++ для первого курса - C++
Здравствуйте. Задали написать программу для решения этой формулы: Составил вот такой код: #include &lt;cstdio&gt; #include &lt;cmath&gt; ...

Лучшая задача для практики - C++
Привет. Что посоветуете для практики? Я было писал разную чушь типо крестиков-ниликов, кубиков, но без псевдографики. Дело в том, что читаю...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru