Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<fstream>
- #include<string>
- #include<vector>
- #include<utility>
- #include<algorithm>
- #include<climits>
- #include<set>
- #include<map>
- #include<cmath>
- #include<iomanip>
- #include<iterator>
- #include<queue>
- #include<stack>
- #include<cctype>
- #include<deque>
- #include <unordered_map>
- #include <unordered_set>
- #include <bitset>
- //by Skeef79
- //НЕ ИСПОЛЬЗУЙ endl, есть свой en!!
- //Иногда нужно не просто придумывать решение, а метматически расписать систему уравнений
- //для задач с cin/cout в большом кол-ве - gnu , иначе вижуалки. А ваще пробуй два если TL
- //для интерактивок - cout<<flush
- // cin.tie и sync_with_stdio убирать для интерактивок
- typedef long long ll;
- typedef long double ld;
- #pragma warning(disable : 4996)
- #pragma comment(linker, "/STACK:16777216")
- #define pb push_back
- #define en '\n'
- #define for0(i,n) for(int i = 0;i<n;i++)
- #define all(x) (x).begin(),(x).end()
- #define allr(x) (x).rbegin(),(x).rend()
- #define vec vector
- using namespace std;
- const int INF = 1000000000 + 1233;
- const ll LINF = 1000000000000000000 + 1233;
- template<typename T> void print(vector<T>& a)
- {
- for (int i = 0; i < a.size(); i++)
- cout << a[i] << ' ';
- }
- template <typename T> void Input(vector<T>& a)
- {
- for (int i = 0; i < a.size(); i++)
- cin >> a[i];
- }
- struct pt {
- ll x, y;
- };
- bool cmp(pt a, pt b) {
- return a.x < b.x || a.x == b.x && a.y < b.y;
- }
- bool cw(pt a, pt b, pt c) {
- return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
- }
- bool ccw(pt a, pt b, pt c) {
- return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
- }
- void convex_hull(vector<pt>& a) {
- if (a.size() == 1) return;
- sort(a.begin(), a.end(), &cmp);
- pt p1 = a[0], p2 = a.back();
- vector<pt> up, down;
- up.push_back(p1);
- down.push_back(p1);
- for (size_t i = 1; i < a.size(); ++i) {
- if (i == a.size() - 1 || cw(p1, a[i], p2)) {
- while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], a[i]))
- up.pop_back();
- up.push_back(a[i]);
- }
- if (i == a.size() - 1 || ccw(p1, a[i], p2)) {
- while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], a[i]))
- down.pop_back();
- down.push_back(a[i]);
- }
- }
- a.clear();
- for (size_t i = 0; i < up.size(); ++i)
- a.push_back(up[i]);
- for (size_t i = down.size() - 2; i > 0; --i)
- a.push_back(down[i]);
- }
- struct aaa {
- int i1, i2, j1, j2;
- aaa(int i1, int j1, int i2, int j2) {
- this->i1 = i1;
- this->i2 = i2;
- this->j1 = j1;
- this->j2 = j2;
- }
- };
- int n, m;
- bool check(int x, int y, vec<vec<char>> &g) {
- if (x < 0 || y < 0 || x >= n || y >= m || g[x][y] == '#')
- return false;
- return true;
- }
- vec<int> dx = { 1, -1, 0, 0 };
- vec<int> dy = { 0, 0, 1, -1 };
- int main()
- {
- //ios::sync_with_stdio(false);
- //cin.tie(0);
- //cout.tie(0);
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- #endif
- //freopen("shield.in", "r", stdin);
- //freopen("shield.out", "w", stdout);
- cin >> n >> m;
- int xi, xj;
- vec<vec<char>> g(n, vec<char>(m));
- for0(i, n) {
- for0(j, m) {
- cin >> g[i][j];
- if (g[i][j] == 'X') {
- xi = i;
- xj = j;
- }
- }
- }
- vec < vec < vec < vec <ll>>>> d(n, vec<vec<vec<ll>>>(m, vec<vec<ll>>(n, vec<ll>(m, - 1))));
- queue<aaa> q;
- q.push(aaa(0, 0, xi, xj));
- d[0][0][xi][xj] = 0;
- while (!q.empty()) {
- aaa v = q.front();
- q.pop();
- for (int i = 0; i < 4; i++) {
- int newx = v.i1 + dx[i];
- int newy = v.j1 + dy[i];
- if (!check(newx, newy, g))
- continue;
- int newx2 = v.i2;
- int newy2 = v.j2;
- if (g[newx][newy] == 'X') {
- newx2 = v.i1;
- newy2 = v.j1;
- }
- if (d[newx][newy][newx2][newy2] != -1) {
- continue;
- }
- d[newx][newy][newx2][newy2] = d[v.i1][v.j1][v.i2][v.j2] + 1;
- cout << newx2 << " " << newy2 << en;
- if (newx2 == 0 && newy2 == 0) {
- cout << d[newx][newy][newx2][newy2];
- return 0;
- }
- q.push(aaa(newx, newy, newx2, newy2));
- }
- }
- cout << "Impossible";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement