結果

問題 No.2897 ２集合間距離
ユーザー vjudge1vjudge1
提出日時 2024-09-25 15:37:54
言語 C++17(clang)
(17.0.6 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
23,936 KB
testcase_01 AC 33 ms
23,808 KB
testcase_02 AC 33 ms
23,936 KB
testcase_03 AC 33 ms
23,936 KB
testcase_04 AC 32 ms
23,936 KB
testcase_05 AC 32 ms
24,064 KB
testcase_06 AC 33 ms
24,064 KB
testcase_07 AC 31 ms
24,064 KB
testcase_08 AC 32 ms
24,064 KB
testcase_09 AC 32 ms
23,936 KB
testcase_10 AC 35 ms
23,936 KB
testcase_11 AC 34 ms
23,808 KB
testcase_12 AC 37 ms
24,064 KB
testcase_13 AC 36 ms
24,064 KB
testcase_14 AC 45 ms
24,064 KB
testcase_15 AC 49 ms
24,192 KB
testcase_16 AC 230 ms
25,600 KB
testcase_17 AC 237 ms
25,600 KB
testcase_18 AC 227 ms
25,600 KB
testcase_19 AC 237 ms
25,600 KB
testcase_20 AC 225 ms
25,600 KB
testcase_21 AC 221 ms
25,472 KB
testcase_22 AC 213 ms
25,600 KB
testcase_23 AC 208 ms
25,472 KB
権限があれば一括ダウンロードができます

ソースコード

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