結果

問題 No.2897 ２集合間距離
ユーザー vjudge1
提出日時 2024-09-25 15:37:54
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 237 ms / 3,500 ms
コード長 1,017 bytes
コンパイル時間 2,854 ms
コンパイル使用メモリ 228,968 KB
実行使用メモリ 25,600 KB
最終ジャッジ日時 2024-09-25 15:38:01
合計ジャッジ時間 6,370 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;
const int M = 2e5 + 5;

struct Node{
  int x, y, cnt;
}que[N * N];

int n, m, head = 1, tail, dist[N][N];
bool vis[N][M];
pair<int, int> a[M];

void Record(int x, int y, int cnt){
  if(x < 0 || x >= N - 5 || y < 0 || y >= N - 5 || vis[x][y]) return ;
  dist[x][y] = cnt, vis[x][y] = 1;
  que[++tail] = {x, y, cnt};
}

int main(){
  cin >> n;
  for(int i = 0; i < N - 5; i++){
    for(int j = 0; j < N - 5; j++) dist[i][j] = N * N + N * N;
  }
  for(int i = 1, x, y; i <= n; i++){
    cin >> x >> y;
    Record(x, y, 0);
  }
  cin >> m;
  for(int i = 1; i <= m; i++){
    cin >> a[i].first >> a[i].second;
  }
  while(head <= tail){
    Node q = que[head++];
    Record(q.x - 1, q.y, q.cnt + 1);
    Record(q.x + 1, q.y, q.cnt + 1);
    Record(q.x, q.y - 1, q.cnt + 1);
    Record(q.x, q.y + 1, q.cnt + 1);
  }
  int ans = INT_MAX;
  for(int i = 1; i <= m; i++){
    ans = min(ans, dist[a[i].first][a[i].second]);
  }
  cout << ans;
  return 0;
}
0