Advertisement
Guest User

Untitled

a guest
May 28th, 2016
1,477
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dx[] = {1,-1,0,0};
  5. int dy[] = {0,0,1,-1};
  6. int n,m,a,b,k,l,g[1001][1001];
  7. pair<int,int> pos[100001];
  8. int main()
  9. {
  10.     int t=1;
  11.     ios_base::sync_with_stdio(false);
  12.     while (scanf("%d %d", &m, &n) && (n||m))
  13.     {
  14.         if (t>1) printf("\n");
  15.         for (int i = 0; i < n; i++)
  16.             for (int j = 0; j < m; j++)
  17.                 g[i][j] = 0;
  18.         scanf("%d", &k);
  19.         queue<pair<int,int>> q;
  20.         for (int i = 0; i < k; i++)
  21.         {
  22.             scanf("%d %d", &a, &b); a--; b--;
  23.             pos[i] = {a,b};
  24.         }
  25.         sort(pos,pos+k);
  26.         for (int i = 0; i < k; i++)
  27.         {
  28.             g[pos[i].first][pos[i].second] = i+1;
  29.             q.push(pos[i]);
  30.         }
  31.         while (!q.empty())
  32.         {
  33.             pair<int,int> root = q.front(); q.pop();
  34.             int x = root.first, y = root.second, v = g[x][y];
  35.             for (int i = 0; i < 4; i++)
  36.                 if (x+dx[i] >= 0 && x+dx[i] < n && y+dy[i] >= 0 && y+dy[i] < m && !g[x+dx[i]][y+dy[i]])
  37.                 {
  38.                     g[x+dx[i]][y+dy[i]] = v;
  39.                     q.push({x+dx[i],y+dy[i]});
  40.                 }
  41.         }
  42.         scanf("%d", &l);
  43.         for (int i = 0; i < l; i++)
  44.         {
  45.             scanf("%d %d", &a, &b); a--; b--;
  46.             printf("%d %d\n", pos[g[a][b]-1].first+1, pos[g[a][b]-1].second+1);
  47.         }
  48.     }
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement