Advertisement
Guest User

Untitled

a guest
Apr 5th, 2020
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <queue>
  8.  
  9. #define MOD 1000000007
  10.  
  11. using namespace std;
  12.  
  13. struct Point
  14. {
  15.     int row, column;
  16. };
  17.  
  18. int columns, rows, vigilants, column, row;
  19. bool visited[1005][1005];
  20. int di[4] = { -1, 0, 1, 0 };
  21. int dj[4] = { 0, 1, 0, -1 };
  22.  
  23. int calculateDistance(Point a, Point b)
  24. {
  25.     return ceil(sqrt((pow(abs(a.row - b.row), 2)) + (pow(abs(a.column - b.column), 2))));
  26. }
  27.  
  28. void calculateForbiddenPoints(Point pos)
  29. {
  30.     int lastRight = pos.column + 10;
  31.     int lastLeft = pos.column - 10;
  32.     int lastUp = pos.row - 10;
  33.     int lastDown = pos.row + 10;
  34.     for (int i = pos.column; i <= lastRight && i <= columns; i++)
  35.         visited[pos.row][i] = true;
  36.     for (int i = pos.column; i >= lastLeft && i >= 0; i--)
  37.         visited[pos.row][i] = true;
  38.     for (int i = pos.row; i <= lastDown && i <= rows; i++)
  39.         visited[i][pos.column] = true;
  40.     for (int i = pos.row; i >= lastUp && i >= 0; i--)
  41.         visited[i][pos.column] = true;
  42.     lastUp = pos.row - 10;
  43.     lastRight = pos.column + 10;
  44.     for (int i = lastUp; i <= pos.row; i++)
  45.     {
  46.         for (int j = pos.column; j <= lastRight; j++)
  47.         {
  48.             if (calculateDistance(pos, { i, j }) <= 10)
  49.             {
  50.                 if (i <= rows && j <= columns && i >= 0 && j >= 0)
  51.                     visited[i][j] = true;
  52.                 int posIzdaArriba = pos.column + (pos.column - j);
  53.                 if (posIzdaArriba >= 0 && i >= 0)
  54.                     visited[i][posIzdaArriba] = true;
  55.                 int posDerechaAbajo = pos.row + (pos.row - i);
  56.                 if (posDerechaAbajo <= rows)
  57.                     visited[posDerechaAbajo][j] = true;
  58.                 if (posIzdaArriba >= 0 && posDerechaAbajo <= rows)
  59.                     visited[posDerechaAbajo][posIzdaArriba] = true;
  60.             }
  61.         }
  62.     }
  63. }
  64.  
  65. bool bfs(Point start)
  66. {
  67.     visited[start.row][start.column] = true;
  68.     queue<Point> q;
  69.     q.push(start);
  70.     Point current;
  71.     while (!q.empty())
  72.     {
  73.         current = q.front(), q.pop();
  74.  
  75.         if (current.row == 0)
  76.             return true;
  77.  
  78.         for (int i = 0; i < 4; i++)
  79.         {
  80.             int row = current.row, column = current.column;
  81.  
  82.             row += di[i];
  83.             column += dj[i];
  84.  
  85.             if (row >= 0 && column >= 0 && row <= rows && column <= columns && !visited[row][column])
  86.             {
  87.                 visited[row][column] = true;
  88.                 q.push({ row, column });
  89.             }
  90.         }
  91.     }
  92.     return false;
  93. }
  94.  
  95. int main()
  96. {
  97.     while (cin >> columns && columns != 0)
  98.     {
  99.         cin >> rows >> vigilants;
  100.         for (int i = 0; i <= rows; i++)
  101.             for (int j = 0; j <= columns; j++)
  102.                 visited[i][j] = false;
  103.         for (int i = 0; i < vigilants; i++)
  104.         {
  105.             cin >> column >> row;
  106.             calculateForbiddenPoints({ row, column });
  107.         }
  108.         int flag = false;
  109.         for (int i = 0; i <= columns && !flag; i++)
  110.         {
  111.             if (!visited[rows][i])
  112.             {
  113.                 if (bfs({ rows, i }))
  114.                 {
  115.                     flag = true;
  116.                     cout << "SI" << endl;
  117.                     break;
  118.                 }
  119.             }
  120.         }
  121.         if (!flag)
  122.             cout << "NO" << endl;
  123.     }
  124.     return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement