Advertisement
roxannemafteiu

cartite

Feb 27th, 2017
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.41 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 0X3f3f3f3f;
  6. const int N_MAX = 205;
  7. const int dx[] = {0, -1, 1, 0, 0, -1, -1, 1, 1, 2, -2, 0, 0};
  8. const int dy[] = {0, 0, 0, -1, 1, -1, 1, 1, -1, 0, 0, 2, -2};
  9.  
  10. int min_line, min_column, min_distance = INF;
  11. int p, n, m, xc, yc, k, g;
  12. int mat[N_MAX][N_MAX];
  13.  
  14. vector <int> graph[N_MAX * N_MAX];
  15.  
  16. void initialise() {
  17.     int inc = 1;
  18.     for (int i = 1; i <= n; ++i) {
  19.         for (int j = 1; j <= m; ++j) {
  20.             mat[i][j] = inc;
  21.             ++inc;
  22.         }
  23.     }
  24. }
  25.  
  26. inline bool isValid(int l, int c) {
  27.     return (l >= 1 && l <= n && c >= 1 && c <= m);
  28. }
  29.  
  30. void foax(int l, int c, int r) {
  31.     int action;
  32.     if (r == 0) action = 1;
  33.     else if (r == 1) action = 5;
  34.     else action = 13;
  35.  
  36.     for (int d = 0; d < action; ++d) {
  37.         int nl = l + dx[d], nc = d + dy[d];
  38.         if (isValid(nl, nc)) mat[nl][nc] = 0;
  39.     }
  40. }
  41.  
  42. void update_neighbours() {
  43.     for (int i = 1; i <= n; ++i) {
  44.         for (int j = 1; j <= m; ++j) {
  45.             if (mat[i][j] != 0) {
  46.                 for (int d = 1; d < 5; ++d) {
  47.                     int nl = i + dx[d], nc = j + dy[d];
  48.                     if (isValid(nl, nc) && mat[nl][nc] != 0) {
  49.                         graph[mat[i][j]].emplace_back(mat[nl][nc]);
  50.                     }
  51.                 }
  52.             }
  53.         }
  54.     }
  55. }
  56.  
  57. inline bool isNeighbour(int sx, int sy, int fx, int fy) {
  58.     for (int d = 1; d < 5; ++d) {
  59.         int nl = sx + dx[d], nc = sy + dy[d];
  60.         if (nl == fx && nc == fy) {
  61.             return true;
  62.         }
  63.     }
  64.  
  65.     return false;
  66. }
  67.  
  68. void read() {
  69.     ifstream fin("cartite.in");
  70.  
  71.     fin >> p >> n >> m >> xc >> yc >> k;
  72.  
  73.     initialise();
  74.     for (int i = 0; i < k; ++i) {
  75.         int x, y, r;
  76.         fin >> x >> y >> r;
  77.         foax(x, y, r);
  78.     }
  79.     update_neighbours();
  80.  
  81.     fin >> g;
  82.     galeries.resize(g);
  83.     for (auto &i : galeries) {
  84.         fin >> i.start_x >> i.start_y >> i.end_x >> end_y;
  85.         i.first = mat[i.start_x][i.start_y];
  86.         i.second = mat[i.end_x][i.end_y];
  87.         if (isNeighbour(i.start_x, i.start_y, i.end_x, i.end_y) == false) {
  88.             graph[i.first].emplace_back(i.second);
  89.             graph[i.second].emplace_back(i.first);
  90.         }
  91.     }
  92.  
  93.     fin.close();
  94. }
  95.  
  96. void bfs() {
  97.     auto total_nodes = n * m + 1;
  98.     bitset <total_nodes> state;
  99.     vector <int> road(total_nodes, 0);
  100.     queue <int> q;
  101.  
  102.     road[mat[xc][xy]] = 0;
  103.     q.emplace(mat[xc][xy]);
  104.  
  105.     while (!q.empty) {
  106.         int node = q.front();
  107.         state.set(node);
  108.  
  109.         for (const auto &son : graph[node]) {
  110.             if (!state[son]) {
  111.                 state.set(son);
  112.                 road[son] = road[node] + 1;
  113.                 q.emplace(son);
  114.             }
  115.         }
  116.     }
  117.  
  118.     for (const auto &i : galeries) {
  119.         if (min_dist > road[i.first]) {
  120.             min_dist = road[i.first];
  121.             min_line = i.start_x;
  122.             min_column = i.start_y;
  123.         }
  124.  
  125.         if (min_dist > road[i.second]) {
  126.             min_dist = road[i.second];
  127.             min_line = i.end_x;
  128.             min_column = i.end_y;
  129.         }
  130.     }
  131. }
  132.  
  133. void write() {
  134.     ofstream fout("cartite.out");
  135.  
  136.     if (p == 1) {
  137.         bfs();
  138.         fout << min_line << ' ' << min_column << ' ' << min_dist;
  139.     } else {
  140.  
  141.     }
  142.  
  143.     fout.close();
  144. }
  145.  
  146. int main() {
  147.     read();
  148.     write();
  149.     return 0;
  150. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement