結果

問題 No.2897 ２集合間距離
コンテスト
ユーザー vjudge1
提出日時 2024-09-25 15:37:54
言語 C++17(clang)
(clang++ 22.1.2 + boost 1.89.0)
コンパイル:
clang++ -O2 -lm -std=c++1z -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 166 ms / 3,500 ms
コード長 1,017 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,841 ms
コンパイル使用メモリ 222,644 KB
実行使用メモリ 25,856 KB
最終ジャッジ日時 2026-04-12 19:37:26
合計ジャッジ時間 4,558 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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