Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <queue>
- #define MOD 1000000007
- using namespace std;
- struct Point
- {
- int row, column;
- };
- int columns, rows, vigilants, column, row;
- bool visited[1005][1005];
- int di[4] = { -1, 0, 1, 0 };
- int dj[4] = { 0, 1, 0, -1 };
- int calculateDistance(Point a, Point b)
- {
- return ceil(sqrt((pow(abs(a.row - b.row), 2)) + (pow(abs(a.column - b.column), 2))));
- }
- void calculateForbiddenPoints(Point pos)
- {
- int lastRight = pos.column + 10;
- int lastLeft = pos.column - 10;
- int lastUp = pos.row - 10;
- int lastDown = pos.row + 10;
- for (int i = pos.column; i <= lastRight && i <= columns; i++)
- visited[pos.row][i] = true;
- for (int i = pos.column; i >= lastLeft && i >= 0; i--)
- visited[pos.row][i] = true;
- for (int i = pos.row; i <= lastDown && i <= rows; i++)
- visited[i][pos.column] = true;
- for (int i = pos.row; i >= lastUp && i >= 0; i--)
- visited[i][pos.column] = true;
- lastUp = pos.row - 10;
- lastRight = pos.column + 10;
- for (int i = lastUp; i <= pos.row; i++)
- {
- for (int j = pos.column; j <= lastRight; j++)
- {
- if (calculateDistance(pos, { i, j }) <= 10)
- {
- if (i <= rows && j <= columns && i >= 0 && j >= 0)
- visited[i][j] = true;
- int posIzdaArriba = pos.column + (pos.column - j);
- if (posIzdaArriba >= 0 && i >= 0)
- visited[i][posIzdaArriba] = true;
- int posDerechaAbajo = pos.row + (pos.row - i);
- if (posDerechaAbajo <= rows)
- visited[posDerechaAbajo][j] = true;
- if (posIzdaArriba >= 0 && posDerechaAbajo <= rows)
- visited[posDerechaAbajo][posIzdaArriba] = true;
- }
- }
- }
- }
- bool bfs(Point start)
- {
- visited[start.row][start.column] = true;
- queue<Point> q;
- q.push(start);
- Point current;
- while (!q.empty())
- {
- current = q.front(), q.pop();
- if (current.row == 0)
- return true;
- for (int i = 0; i < 4; i++)
- {
- int row = current.row, column = current.column;
- row += di[i];
- column += dj[i];
- if (row >= 0 && column >= 0 && row <= rows && column <= columns && !visited[row][column])
- {
- visited[row][column] = true;
- q.push({ row, column });
- }
- }
- }
- return false;
- }
- int main()
- {
- while (cin >> columns && columns != 0)
- {
- cin >> rows >> vigilants;
- for (int i = 0; i <= rows; i++)
- for (int j = 0; j <= columns; j++)
- visited[i][j] = false;
- for (int i = 0; i < vigilants; i++)
- {
- cin >> column >> row;
- calculateForbiddenPoints({ row, column });
- }
- int flag = false;
- for (int i = 0; i <= columns && !flag; i++)
- {
- if (!visited[rows][i])
- {
- if (bfs({ rows, i }))
- {
- flag = true;
- cout << "SI" << endl;
- break;
- }
- }
- }
- if (!flag)
- cout << "NO" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement