Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define flash ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
- #define stop return 0
- #define pb push_back
- #define ll long long
- #define dbg(x) cerr << #x << " = " << x << "\n" ;
- #define ff first
- #define ss second
- /*
- #pragma GCC target ("avx2")
- #pragma GCC optimization ("O3")
- #pragma comment (linker, "/stack:200000000")
- #pragma GCC optimize("Ofast")
- #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- */
- const long long INF = 1e9 + 7;
- const double MIN = 1e-6;
- const long long ARR = 1e6 + 11;
- const long long DRR = 1e3 + 11;
- const long long MOD = 12347;
- const int maxn = 2e5 + 10;
- int n, m;
- int dst[2111][2111];
- queue <pair <int, int> > q;
- pair <int, int> col[] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1}};
- void press_F_() {
- cin >> n >> m;
- if (n == 1) {
- int x, y, t;
- cin >> x >> y >> t;
- int mx = 0;
- int ans1, ans2, ans3, ans4;
- ans1 = max(abs(m - y), abs(m - x));
- ans2 = max(abs(1 - y), abs(m - x));
- ans3 = max(abs(m - y), abs(1 - x));
- ans4 = max(abs(1 - y), abs(1 - x));
- cout << max(max(ans1, ans2), max(ans3, ans4)) + t - 1;
- return;
- }
- for (int i = 1; i <= m; i++) {
- for (int j = 1; j <= m; j++) {
- dst[i][j] = INF;
- }
- }
- for (int i = 1; i <= n; i++) {
- int x, y, t;
- cin >> x >> y >> t;
- dst[x][y] = t;
- q.push({x, y});
- }
- while(!q.empty()) {
- pair <int, int> v;
- v = q.front();
- q.pop();
- for (int i = 0; i < 8; i++) {
- int dx = v.ff + col[i].ff, dy = v.ss + col[i].ss;
- if (dx >= 1 && dx <= m && dy >= 1 && dy <= m) {
- if (dst[dx][dy] > dst[v.ff][v.ss] + 1) {
- dst[dx][dy] = dst[v.ff][v.ss] + 1;
- q.push({dx, dy});
- }
- }
- }
- }
- int mx = 0, pos1, pos2;
- for (int i = 1; i <= m; i++) {
- for (int j = 1; j <= m; j++) {
- if (dst[i][j] > mx) {
- mx = dst[i][j];
- }
- }
- }
- cout << mx - 1;
- }
- int main() {
- flash;
- int T = 1;
- //cin >> T;
- for (int i = 1; i <= T; i++) {
- // cout << "Case" << " " << i << ':' << " ";
- press_F_();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
