fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define end "\n"
  6. #define vi vector<int>
  7. #define all(v) v.begin(), v.end()
  8. #define SORT(v) sort(all(v))
  9. #define SORTX(v) sort(v.begin(), v.end(), greater<int>())
  10. #define read(a) for (auto &i : a) cin >> i
  11. #define Printv(a) for (auto &i : a) cout << i << " "
  12. #define M_ShahaT ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  13.  
  14. /*
  15.     وَأَن لَّيْسَ لِلْإِنسَانِ إِلَّا مَا سَعَى ﴿39﴾
  16.     وَأَنَّ سَعْيَهُ سَوْفَ يُرَى ﴿40﴾
  17.     ثُمَّ يُجْزَاهُ الْجَزَاء الْأَوْفَى ﴿41﴾
  18. */
  19.  
  20. void FIO(){
  21.  
  22.  #ifndef ONLINE_JUDGE
  23. freopen("Input.txt","r",stdin);
  24. freopen("Output.txt","w",stdout);
  25. #endif
  26.  
  27. }
  28. double const PI=acos(-1.0);
  29. int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
  30. int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
  31. char di[] = {'D', 'L', 'U', 'R'};
  32. const int N=1e6;
  33. int n,m;
  34. vector<vector<int>>dis;
  35. vector<pair<int,int>>f;
  36. int k;
  37. bool valid(int x,int y){
  38.     return x>=0 &&  x<n && y>=0 && y<m ;
  39. }
  40. void bfs(){
  41.     queue<pair<int,int>>q;
  42.     for(int i=0;i<k;i++){
  43.         q.push(f[i]);
  44.         dis[f[i].first][f[i].second]=0;
  45.     }
  46.     while(!q.empty()){
  47.         pair<int,int>cur=q.front();q.pop();
  48.         int x=cur.first;int y=cur.second;
  49.         for(int i=0;i<4;i++){
  50.             int nx=x+dx[i];int ny=y+dy[i];
  51.             if(valid(nx,ny)&&dis[nx][ny]==-1){
  52.                 q.push({nx,ny});
  53.                 dis[nx][ny]=dis[x][y]+1;
  54.             }
  55.         }
  56.     }
  57. }
  58. void solve_case() {
  59.     cin>>n>>m>>k;
  60.  
  61. f.assign(k,{-1,-1});
  62. dis.assign(n,vector<int>(m,-1));
  63.  
  64. for(int i=0;i<k;i++){
  65.     pair<int,int>a;
  66.     cin>>a.first>>a.second;a.first--;a.second--;
  67.     f[i]=a;
  68. }
  69.  
  70. bfs();
  71. pair<int,int>to_print;
  72. int mx=-2;
  73. for(int i=0;i<n;i++){
  74.     for(int j=0;j<m;j++){
  75.         if(mx<dis[i][j]){
  76.             to_print={i,j};
  77.             mx=max(dis[i][j],mx);
  78.         }
  79.     }
  80. }
  81. cout<<to_print.first+1<<" "<<to_print.second+1;
  82.  
  83. }
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93. int main(){
  94.  M_ShahaT
  95. FIO();
  96.  
  97.  int t=1;
  98.  
  99. //cin >> t;
  100.     for(int i=1;i<=t;i++){
  101.  
  102.         solve_case();
  103.  
  104.     }
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 1
https://ideone.com/nMEhFg
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!