bool go int st int en int size bool flag fflag std vector std pair int

 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
bool go(int st, int en, int size)
{
bool flag=1,fflag;
std::vector <std::pair<int,int>> closedList; // закрытый список
std::vector <std::pair<int,int>> openList; // открытый список
const int dx[4]={1,0,-1,0}; // смещения по х
const int dy[4]={0,1,0,-1}; // смещения по у
int level=0,fmin,choose,nx,ny;
for (int i=0;i<size;++i)
for (int j=0;j<size;++j)
if (m[i][j].value!=444) m[i][j].value = -1;
start.second = st/size;
start.first = st%size;
finish.second=en/size;
finish.first=en%size;
openList.push_back(std::pair<int,int>(start.first,start.second)); // добавляем начало в открытый список
m[start.first][start.second].value=level; // задаем все значения
m[start.first][start.second].g=0;
m[start.first][start.second].h=estimate(start.first,start.second);
m[start.first][start.second].f=m[start.first][start.second].g+m[start.first][start.second].h;
fflag=1;
closedList.clear(); // еще раз обнуляем закрытый список. Зачем? я параноик.
while (openList.size() > 0 && std::find(closedList.begin(),closedList.end(),std::pair<int,int>(finish.first,finish.second))==closedList.end()) // перебираем либо пока есть открытый, либо когда не найдем конец
{
fmin=(fflag)?m[openList[0].first][openList[0].second].diff:m[openList[0].first][openList[0].second].f; // для сравнения
choose=0; // индекс для сравнения
for (unsigned int i=0; i<openList.size(); ++i) // перебор вершин открытого списка
{
if (fflag) m[openList[i].first][openList[i].second].f=m[openList[i].first][openList[i].second].diff;
if (m[openList[i].first][openList[i].second].f<fmin)
{
choose=i;
fmin=m[openList[i].first][openList[i].second].f; // поиск наиболее приоритетной ячейки
}
}
fflag=0;
level=m[openList[choose].first][openList[choose].first].diff+level;
closedList.push_back(openList[choose]); // добавим в закрытый список ее
for (int h=0; h<4; ++h) // перебор ее соседей
{
nx = openList[choose].first+dx[h];
ny = openList[choose].second+dy[h];
level=m[openList[choose].first][openList[choose].second].value; // пересчет уровня
if (flag && nx<size && nx>=0 && ny>=0 && ny<size) // проверка на нахождение конца и вылет за пределы матрицы
if (m[nx][ny].value!=444 && std::find(closedList.begin(),closedList.end(),std::pair<int,int>(nx,ny))==closedList.end()) // если не стенка и если вершины нету в закрытом
{
if (!(m[nx][ny].value!=-1 && m[nx][ny].value<level+m[nx][ny].diff)){
openList.push_back(std::pair<int,int>(nx,ny)); // добавляем в открытый список
m[nx][ny].g=level; // пересчет значений
m[nx][ny].value=level+m[nx][ny].diff;
m[nx][ny].h=estimate(nx,ny);
m[nx][ny].f=m[nx][ny].g+m[nx][ny].h;
if (nx == finish.first && ny == finish.second) flag=0; //если конец - шалость удалась
}
}
}
openList.erase(openList.begin()+choose);
}
path_w.clear();
if (!flag) //сборка обратного пути
{
int x=finish.first;
int y=finish.second;
path_w.push_back(std::pair<int,int>(x,y));
while (m[x][y].value!=0)
for (int d=0; d<4; ++d)
{
nx=x+dx[d];
ny=y+dy[d];
if (nx<size && nx>=0 && ny>=0 && ny<size)
if (m[x][y].value-m[x][y].diff==m[nx][ny].value)
{
x=nx;
y=ny;
path_w.push_back(std::pair<int,int>(nx,ny));
break;
}
}
path_w.push_back(std::pair<int,int>(start.first,start.second));
}
return !flag;