Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Factor común
- */
- #include <algorithm>
- #include <iostream>
- #include <iterator>
- #include <iomanip>
- #include <sstream>
- #include <fstream>
- #include <cassert>
- #include <climits>
- #include <cstdlib>
- #include <cstring>
- #include <string>
- #include <cstdio>
- #include <vector>
- #include <cmath>
- #include <queue>
- #include <deque>
- #include <stack>
- #include <list>
- #include <map>
- #include <set>
- using namespace std;
- template <class T> string toStr(const T &x){ stringstream s; s << x; return s.str(); }
- template <class T> int toInt(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
- #define For(i, a, b) for (int i=(a); i<(b); ++i)
- #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
- #define D(x) cout << #x " = " << (x) << endl;
- const double EPS = 1e-9;
- int cmp(double x, double y = 0, double tol = EPS){
- return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
- }
- //#define LECTURA_ARCHIVO
- #define ARCHIVO ""
- const int MAXN = 1005;
- int score[MAXN][MAXN];
- int X, Y;
- int d[MAXN][MAXN];
- pair<int, int> start, end;
- int dx[] = {-1, +1, +0, +0};
- int dy[] = {+0, +0, -1, +1};
- bool inside(int x, int y){
- return 0 <= x && x < X && 0 <= y && y < Y;
- }
- bool llega(int cota){
- //printf("llega con %d?\n", cota);
- memset(d, -1, sizeof d);
- queue<pair<int, int> > q;
- q.push(start);
- d[start.first][start.second] = 0;
- if (score[start.first][start.second] < cota) return false;
- while (q.size()){
- int x = q.front().first, y = q.front().second;
- q.pop();
- //printf("popped (%d, %d), score = %d\n", x, y, score[x][y]);
- if (make_pair(x, y) == end) return true;
- for (int k=0; k<4; ++k){
- int nx = x + dx[k];
- int ny = y + dy[k];
- if (!inside(nx, ny)) continue;
- if (d[nx][ny] != -1) continue;
- if (score[nx][ny] < cota) continue;
- d[nx][ny] = d[x][y] + 1;
- q.push(make_pair(nx, ny));
- }
- }
- return false;
- }
- int main() {
- #ifdef LECTURA_ARCHIVO
- freopen(ARCHIVO ".in", "r", stdin);
- #endif
- int Casos;
- cin >> Casos;
- while (Casos--){
- int bases;
- cin >> bases >> X >> Y;
- cin >> start.first >> start.second >> end.first >> end.second;
- memset(score, -1, sizeof score);
- queue<pair<int, int> > q;
- for (int i=0; i<bases; ++i){
- int x, y;
- cin >> x >> y;
- q.push(make_pair(x, y));
- score[x][y] = 0;
- }
- //fill score
- while (q.size()){
- int x = q.front().first, y = q.front().second;
- q.pop();
- for (int k=0; k<4; ++k){
- int nx = x + dx[k];
- int ny = y + dy[k];
- if (!inside(nx, ny)) continue;
- if (score[nx][ny] != -1) continue;
- score[nx][ny] = score[x][y] + 1;
- q.push(make_pair(nx, ny));
- }
- }
- //For(i, 0, X){ For(j, 0, Y) printf("%2d ", score[i][j]); puts(""); }
- //llene la matriz, binary search
- int low = 0, high = 3*(X + Y);
- while (low < high){
- int mid = (low + high + 1) / 2;
- if (llega(mid)) low = mid;
- else high = mid - 1;
- }
- assert(low == high);
- assert(llega(low));
- printf("%d %d\n", low, d[end.first][end.second]);
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment