Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <math.h>
- #include <algorithm>
- #include <vector>
- using namespace std;
- long long inf = 1000000000;
- struct edge
- {
- long long a, b, cost;
- };
- pair<long long,long long> solve(long long n, long long m, long long v, vector<edge>& e, vector<long long>& d, vector<long long>& c)
- {
- d[v] = 0;
- long long g = inf;
- long long fc = 0;
- for (long long i = 0; i < n*m - 1; i++)
- {
- for (long long j = 0; j < e.size(); j++)
- {
- if (d[e[j].a] < inf)
- {
- if (d[e[j].b] > d[e[j].a] + e[j].cost)
- {
- d[e[j].b] = d[e[j].a] + e[j].cost;
- }
- }
- long long l = max(c[e[j].b], d[e[j].b]);
- if(l < g)
- {
- g = l;
- fc = e[j].b;
- }
- l = max(c[e[j].a], d[e[j].a]);
- if(l < g)
- {
- g = l;
- fc = e[j].a;
- }
- }
- }
- return pair<long long,long long>(g,fc);
- }
- void solve(long long n, long long m, long long v, vector<edge>& e, vector<long long>& d)
- {
- d[v] = 0;
- for (long long i = 0; i < n*m - 1; i++)
- {
- bool any = false;
- for (long long j = 0; j < e.size(); j++)
- {
- if (d[e[j].a] < inf)
- {
- if (d[e[j].b] > d[e[j].a] + e[j].cost)
- {
- d[e[j].b] = d[e[j].a] + e[j].cost;
- any = true;
- }
- }
- }
- if (!any)
- {
- break;
- }
- }
- }
- int main()
- {
- long long n, m;
- cin >> n >> m;
- long long mas[301][301];
- vector<edge> ec;
- vector<edge> ed;
- vector<long long> c(n*m,inf);
- vector<long long> d(n*m,inf);
- for(long long i = 0; i < n; i++)
- {
- for(long long j = 0; j < m; j++)
- {
- cin >> mas[i][j];
- }
- }
- long long x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- x1--;
- y1--;
- x2--;
- y2--;
- if(x1 == x2 && y1 == y2)
- {
- cout << "0\n" << x1 + 1 << " " << y1 + 1 << "\n";
- return 0;
- }
- long long v1 = x1*m + y1;
- long long v2 = x2*m + y2;
- for(long long i = 0; i < n; i++)
- {
- for(long long j = 0; j < m; j++)
- {
- int masx[4] = {1, -1, 0, 0};
- int masy[4] = {0, 0, 1, -1};
- for(int k = 0; k < 4; k++)
- {
- int ni = masx[k] + i;
- int nj = masy[k] + j;
- if(ni < 0 || ni >= n || nj < 0 || nj >= m)
- continue;
- if(mas[i][j] <= mas[ni][nj])
- {
- struct edge a;
- a.a = i*m+ j;
- a.b = (ni) * m + nj;
- a.cost = 1;
- ec.push_back(a);
- }
- if(mas[i][j] >= mas[ni][nj])
- {
- struct edge a;
- a.a = i*m + j;
- a.b = (ni) * m + nj;
- a.cost = 1;
- ed.push_back(a);
- }
- }
- }
- }
- solve(n, m, v1, ec,d);
- pair<int,int> an = solve(n, m, v2, ed,c,d);
- long long g = an.first;
- long long fc = an.second / m;
- long long fd = an.second % m;
- if(g == inf)
- {
- cout << -1 << "\n";
- return 0;
- }
- else
- {
- cout << g << "\n" << fc + 1 << " " << fd + 1 << "\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement