Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //part one
- #include <iostream>
- #include <cmath>
- #include <iomanip>
- #include <vector>
- #include <random>
- #include <algorithm>
- #define streams freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- using namespace std;
- struct point {
- int x, y;
- int type, f, g, h;
- point *parent;
- bool opened, closed;
- };
- point lab[1000][1000];
- int n, m;
- int startX, startY;
- int endX, endY;
- bool done = false;
- vector <point> visited;
- void getData()
- {
- cin >> n >> m;
- cin >> startX >> startY;
- cin >> endX >> endY;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= m; j++)
- {
- cin >> lab[i][j].type;
- lab[i][j].y = i;
- lab[i][j].x = j;
- }
- }
- void setStartPos()
- {
- lab[startY][startX].g = 1;
- lab[startY][startX].h = endX - startX + endY - startY; //Manhattan distance
- lab[startY][startX].f = lab[startY][startX].g + lab[startY][startX].h;
- lab[startY][startX].opened = true;
- visited.push_back(lab[startY][startX]);
- }
- void check_successor(int dy, int dx, point A)
- {
- if (A.x + dx > 0 && A.x + dx < m + 1 && A.y + dy > 0 && A.y + dy < n + 1 && lab[A.y + dy][A.x + dx].type == 0)
- {
- int cur_f = lab[A.y][A.x].g + 1 + endX - (A.x + dx) + endY - (A.y + dy);
- if (lab[A.y + dy][A.x + dx].x == endX && lab[A.y + dy][A.x + dx].y == endY)
- done = true;
- else
- if (lab[A.y + dy][A.x + dx].opened && lab[A.y + dy][A.x + dx].f <= cur_f)
- return;
- else
- if (lab[A.y + dy][A.x + dx].closed && lab[A.y + dy][A.x + dx].f <= cur_f)
- return;
- lab[A.y + dy][A.x + dx].parent = &lab[A.y][A.x];
- lab[A.y + dy][A.x + dx].g = lab[A.y + dy][A.x + dx].parent -> g + 1;
- lab[A.y + dy][A.x + dx].h = endX - lab[A.y + dy][A.x + dx].x + endY - lab[A.y + dy][A.x + dx].y;
- lab[A.y + dy][A.x + dx].f = lab[A.y + dy][A.x + dx].g + lab[A.y + dy][A.x + dx].h;
- lab[A.y + dy][A.x + dx].opened = true;
- visited.push_back(lab[A.y + dy][A.x + dx]);
- }
- }
- bool comp_func(point a, point b)
- {
- if (a.f > b.f)
- return true;
- else
- return false;
- }
- void print_path(point point)
- {
- if (point.parent != NULL)
- print_path(*point.parent);
- cout << point.x << " " << point.y << endl;
- }
- void JosephJoestar()
- {
- int sup[8] = {-1, 0, 0, 1, 1, 0, 0, -1};
- point tmp;
- while (!visited.empty() && !done)
- {
- tmp = visited.back();
- visited.pop_back();
- lab[tmp.y][tmp.x].opened = false;
- for (int i = 0; i < 8; i += 2)
- {
- if (!done)
- {
- check_successor(sup[i], sup[i + 1], tmp);
- }
- }
- lab[tmp.y][tmp.x].closed = true;
- sort(visited.begin(), visited.end(), comp_func);
- }
- cout << lab[endY][endX].f << endl;
- print_path(lab[endY][endX]);
- }
- int main()
- {
- #ifndef LOCAL
- streams;
- #endif
- getData();
- setStartPos();
- JosephJoestar();
- return 0;
- }
- // part two
- #include <iostream>
- #include <cmath>
- #include <iomanip>
- #include <vector>
- #include <random>
- #include <algorithm>
- #define streams freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- using namespace std;
- struct point {
- int x, y;
- int type, f, g, h;
- point *parent;
- bool opened, closed;
- };
- point lab[1000][1000];
- int n, m;
- int startX, startY;
- int endX, endY;
- bool done = false;
- vector <point> visited;
- void getData()
- {
- cin >> n >> m;
- cin >> startX >> startY;
- cin >> endX >> endY;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= m; j++)
- {
- cin >> lab[i][j].type;
- lab[i][j].y = i;
- lab[i][j].x = j;
- }
- }
- void setStartPos()
- {
- lab[startY][startX].g = 1;
- lab[startY][startX].h = endX - startX + endY - startY;
- lab[startY][startX].f = lab[startY][startX].g + lab[startY][startX].h;
- lab[startY][startX].opened = true;
- visited.push_back(lab[startY][startX]);
- }
- void check_successor(int dy, int dx, point A)
- {
- if (A.x + dx > 0 && A.x + dx < m + 1 && A.y + dy > 0 && A.y + dy < n + 1 && lab[A.y + dy][A.x + dx].type == 0)
- {
- int cur_f = lab[A.y][A.x].g + 1 + endX - (A.x + dx) + endY - (A.y + dy);
- if (lab[A.y + dy][A.x + dx].x == endX && lab[A.y + dy][A.x + dx].y == endY)
- done = true;
- else
- if (lab[A.y + dy][A.x + dx].opened && lab[A.y + dy][A.x + dx].f <= cur_f)
- return;
- else
- if (lab[A.y + dy][A.x + dx].closed && lab[A.y + dy][A.x + dx].f <= cur_f)
- return;
- lab[A.y + dy][A.x + dx].parent = &lab[A.y][A.x];
- lab[A.y + dy][A.x + dx].g = lab[A.y + dy][A.x + dx].parent -> g + 1;
- lab[A.y + dy][A.x + dx].h = endX - lab[A.y + dy][A.x + dx].x + endY - lab[A.y + dy][A.x + dx].y;
- lab[A.y + dy][A.x + dx].f = lab[A.y + dy][A.x + dx].g + lab[A.y + dy][A.x + dx].h;
- lab[A.y + dy][A.x + dx].opened = true;
- visited.push_back(lab[A.y + dy][A.x + dx]);
- }
- }
- bool comp_func(point a, point b)
- {
- if (a.f > b.f)
- return true;
- else
- return false;
- }
- void print_path(point point)
- {
- if (point.parent != NULL)
- print_path(*point.parent);
- cout << point.x << " " << point.y << endl;
- }
- void JosephJoestar()
- {
- int sup[8] = {-1, 0, 0, 1, 1, 0, 0, -1};
- point tmp;
- while (!visited.empty() && !done)
- {
- tmp = visited.back();
- visited.pop_back();
- lab[tmp.y][tmp.x].opened = false;
- for (int i = 0; i < 8; i += 2)
- {
- if (!done)
- {
- check_successor(sup[i], sup[i + 1], tmp);
- }
- }
- lab[tmp.y][tmp.x].closed = true;
- sort(visited.begin(), visited.end(), comp_func);
- }
- cout << lab[endY][endX].f << endl;
- print_path(lab[endY][endX]);
- }
- int main()
- {
- #ifndef LOCAL
- streams;
- #endif
- getData();
- setStartPos();
- JosephJoestar();
- return 0;
- }
- // part three
- #include <iostream>
- #include <cmath>
- #include <iomanip>
- #include <vector>
- #include <random>
- #include <algorithm>
- #define streams freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- using namespace std;
- struct point {
- int x, y;
- int type, f, g, h;
- point *parent;
- bool opened, closed;
- };
- point lab[1000][1000];
- int n, m;
- int startX, startY;
- int endX, endY;
- bool done = false;
- vector <point> visited;
- void getData()
- {
- cin >> n >> m;
- cin >> startX >> startY;
- cin >> endX >> endY;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= m; j++)
- {
- cin >> lab[i][j].type;
- lab[i][j].y = i;
- lab[i][j].x = j;
- }
- }
- void setStartPos()
- {
- lab[startY][startX].g = 1;
- lab[startY][startX].h = endX - startX + endY - startY;
- lab[startY][startX].f = lab[startY][startX].g + lab[startY][startX].h;
- lab[startY][startX].opened = true;
- visited.push_back(lab[startY][startX]);
- }
- void check_successor(int dy, int dx, point A)
- {
- if (A.x + dx > 0 && A.x + dx < m + 1 && A.y + dy > 0 && A.y + dy < n + 1 && lab[A.y + dy][A.x + dx].type == 0)
- {
- int cur_f = lab[A.y][A.x].g + 1 + endX - (A.x + dx) + endY - (A.y + dy);
- if (lab[A.y + dy][A.x + dx].x == endX && lab[A.y + dy][A.x + dx].y == endY)
- done = true;
- else
- if (lab[A.y + dy][A.x + dx].opened && lab[A.y + dy][A.x + dx].f <= cur_f)
- return;
- else
- if (lab[A.y + dy][A.x + dx].closed && lab[A.y + dy][A.x + dx].f <= cur_f)
- return;
- lab[A.y + dy][A.x + dx].parent = &lab[A.y][A.x];
- lab[A.y + dy][A.x + dx].g = lab[A.y + dy][A.x + dx].parent -> g + 1;
- lab[A.y + dy][A.x + dx].h = endX - lab[A.y + dy][A.x + dx].x + endY - lab[A.y + dy][A.x + dx].y;
- lab[A.y + dy][A.x + dx].f = lab[A.y + dy][A.x + dx].g + lab[A.y + dy][A.x + dx].h;
- lab[A.y + dy][A.x + dx].opened = true;
- visited.push_back(lab[A.y + dy][A.x + dx]);
- }
- }
- bool comp_func(point a, point b)
- {
- if (a.f > b.f)
- return true;
- else
- return false;
- }
- void print_path(point point)
- {
- if (point.parent != NULL)
- print_path(*point.parent);
- cout << point.x << " " << point.y << endl;
- }
- void JosephJoestar()
- {
- int sup[8] = {-1, 0, 0, 1, 1, 0, 0, -1};
- point tmp;
- while (!visited.empty() && !done)
- {
- tmp = visited.back();
- visited.pop_back();
- lab[tmp.y][tmp.x].opened = false;
- for (int i = 0; i < 8; i += 2)
- {
- if (!done)
- {
- check_successor(sup[i], sup[i + 1], tmp);
- }
- }
- lab[tmp.y][tmp.x].closed = true;
- sort(visited.begin(), visited.end(), comp_func);
- }
- cout << lab[endY][endX].f << endl;
- print_path(lab[endY][endX]);
- }
- int main()
- {
- #ifndef LOCAL
- streams;
- #endif
- getData();
- setStartPos();
- JosephJoestar();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement