Advertisement
OIQ

task238

OIQ
Nov 5th, 2019
190
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.57 KB | None
  1. #include <iostream>
  2. #include <deque>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. struct point {
  9.     int xi;
  10.     int xj;
  11. };
  12.  
  13. int find(point dot, vector <vector<point>>& g) {
  14.     for (int i = 0; i < g.size(); i++)
  15.         if (g[i][0].xi == dot.xi && g[i][0].xj == dot.xj)
  16.             return i;
  17.  
  18.     return -1;
  19. }
  20.  
  21. int main() {
  22.  
  23.     int n, m;
  24.     cin >> n >> m;
  25.  
  26.     int si, sj;
  27.     cin >> si >> sj;
  28.  
  29.     vector <vector <int>> a(n + 2, vector <int>(m + 2, -2));
  30.  
  31.  
  32.     point start;
  33.     start.xi = si;
  34.     start.xj = sj;
  35.  
  36.     deque <point> deq;
  37.  
  38.     deq.push_back(start);
  39.  
  40.     for (int i = 1; i < n + 1; i++)
  41.         for (int j = 1; j < m + 1; j++) {
  42.             cin >> a[i][j];
  43.             if (a[i][j] == 0)
  44.                 a[i][j] = -1;
  45.             else
  46.                 a[i][j] = -2;
  47.         }
  48.     a[si][sj] = 0;
  49.     int h;
  50.     cin >> h;
  51.  
  52.     vector <vector<point>> g(h, vector<point>(2));
  53.     point gip;
  54.     for (int i = 0; i < h; i++) {
  55.         cin >> gip.xi;
  56.         cin >> gip.xj;
  57.         g[i][0] = gip;
  58.         cin >> gip.xi;
  59.         cin >> gip.xj;
  60.         g[i][1] = gip;
  61.     }
  62.  
  63.     int w;
  64.     cin >> w;
  65.  
  66.     point way;
  67.  
  68.     vector <point> ways(w);
  69.  
  70.     for (int i = 0; i < w; i++) {
  71.         cin >> way.xi;
  72.         cin >> way.xj;
  73.         ways[i] = way;
  74.     }
  75.  
  76.     while (!deq.empty()) {
  77.         point dot = deq.front();
  78.         deq.pop_front();
  79.         point ndot;
  80.  
  81.         int ind = find(dot, g);
  82.  
  83.         if (ind != -1 && a[g[ind][1].xi][g[ind][1].xj] == -1) {
  84.             gip.xi = g[ind][1].xi;
  85.             gip.xj = g[ind][1].xj;
  86.             a[gip.xi][gip.xj] = a[dot.xi][dot.xj] + 1;
  87.             deq.push_back(gip);
  88.         }
  89.         //----------------------------
  90.  
  91.         if (a[dot.xi - 1][dot.xj] == -1) {
  92.             a[dot.xi - 1][dot.xj] = a[dot.xi][dot.xj] + 1;
  93.             ndot.xi = dot.xi - 1;
  94.             ndot.xj = dot.xj;
  95.             deq.push_back(ndot);
  96.         }
  97.         if (a[dot.xi][dot.xj + 1] == -1) {
  98.             a[dot.xi][dot.xj + 1] = a[dot.xi][dot.xj] + 1;
  99.             ndot.xi = dot.xi;
  100.             ndot.xj = dot.xj + 1;
  101.             deq.push_back(ndot);
  102.         }
  103.         if (a[dot.xi + 1][dot.xj] == -1) {
  104.             a[dot.xi + 1][dot.xj] = a[dot.xi][dot.xj] + 1;
  105.             ndot.xi = dot.xi + 1;
  106.             ndot.xj = dot.xj;
  107.             deq.push_back(ndot);
  108.         }
  109.         if (a[dot.xi][dot.xj  - 1] == -1) {
  110.             a[dot.xi][dot.xj - 1] = a[dot.xi][dot.xj] + 1;
  111.             ndot.xi = dot.xi;
  112.             ndot.xj = dot.xj - 1;
  113.             deq.push_back(ndot);
  114.         }
  115.         /*
  116.         for (int i = 0; i < n + 2; i++) {
  117.             for (int j = 0; j < m + 2; j++)
  118.                 cout << a[i][j] << " ";
  119.             cout << endl;
  120.         }
  121.         cout << "-------------------------------"<< endl;
  122.         */
  123.     }
  124.    
  125.     int min = 1000 * 1000;
  126.  
  127.     for (int i = 0; i < ways.size(); i++) {
  128.         if (a[ways[i].xi][ways[i].xj] != -1 && a[ways[i].xi][ways[i].xj] < min)
  129.             min = a[ways[i].xi][ways[i].xj];
  130.     }
  131.  
  132.     if (min == 1000 * 1000)
  133.         cout << "Impossible";
  134.     else
  135.         cout << min + 1;
  136.  
  137.     return 0;
  138. }
Advertisement
RAW Paste Data Copied
Advertisement