Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
BestIn
0 / 0 / 0
Регистрация: 16.05.2013
Сообщений: 10
24.05.2013, 19:19     Задача для лабораторной #1
Помогите пожалуйста написать вот это,очень нужно!Буду очень благодарен.
Задача

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


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

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

C++ Помогите с лабораторной
C++ Нужна ваша помощь, по решению лабораторной(
Помогите!Задача для С C++
C++ Хэлп по лабораторной 2
Лучшая задача для практики C++
Использовать программу, составленную при выполнении лабораторной работы №10 C++
Задание по лабораторной работе C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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;
}
BestIn
0 / 0 / 0
Регистрация: 16.05.2013
Сообщений: 10
04.06.2013, 00:04  [ТС]     Задача для лабораторной #3
ПОМОГИТЕ!
Yandex
Объявления
04.06.2013, 00:04     Задача для лабораторной
Ответ Создать тему
Опции темы

Текущее время: 06:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru