Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int INF = 0X3f3f3f3f;
- const int N_MAX = 205;
- const int dx[] = {0, -1, 1, 0, 0, -1, -1, 1, 1, 2, -2, 0, 0};
- const int dy[] = {0, 0, 0, -1, 1, -1, 1, 1, -1, 0, 0, 2, -2};
- int min_line, min_column, min_distance = INF;
- int p, n, m, xc, yc, k, g;
- int mat[N_MAX][N_MAX];
- vector <int> graph[N_MAX * N_MAX];
- void initialise() {
- int inc = 1;
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= m; ++j) {
- mat[i][j] = inc;
- ++inc;
- }
- }
- }
- inline bool isValid(int l, int c) {
- return (l >= 1 && l <= n && c >= 1 && c <= m);
- }
- void foax(int l, int c, int r) {
- int action;
- if (r == 0) action = 1;
- else if (r == 1) action = 5;
- else action = 13;
- for (int d = 0; d < action; ++d) {
- int nl = l + dx[d], nc = d + dy[d];
- if (isValid(nl, nc)) mat[nl][nc] = 0;
- }
- }
- void update_neighbours() {
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= m; ++j) {
- if (mat[i][j] != 0) {
- for (int d = 1; d < 5; ++d) {
- int nl = i + dx[d], nc = j + dy[d];
- if (isValid(nl, nc) && mat[nl][nc] != 0) {
- graph[mat[i][j]].emplace_back(mat[nl][nc]);
- }
- }
- }
- }
- }
- }
- inline bool isNeighbour(int sx, int sy, int fx, int fy) {
- for (int d = 1; d < 5; ++d) {
- int nl = sx + dx[d], nc = sy + dy[d];
- if (nl == fx && nc == fy) {
- return true;
- }
- }
- return false;
- }
- void read() {
- ifstream fin("cartite.in");
- fin >> p >> n >> m >> xc >> yc >> k;
- initialise();
- for (int i = 0; i < k; ++i) {
- int x, y, r;
- fin >> x >> y >> r;
- foax(x, y, r);
- }
- update_neighbours();
- fin >> g;
- galeries.resize(g);
- for (auto &i : galeries) {
- fin >> i.start_x >> i.start_y >> i.end_x >> end_y;
- i.first = mat[i.start_x][i.start_y];
- i.second = mat[i.end_x][i.end_y];
- if (isNeighbour(i.start_x, i.start_y, i.end_x, i.end_y) == false) {
- graph[i.first].emplace_back(i.second);
- graph[i.second].emplace_back(i.first);
- }
- }
- fin.close();
- }
- void bfs() {
- auto total_nodes = n * m + 1;
- bitset <total_nodes> state;
- vector <int> road(total_nodes, 0);
- queue <int> q;
- road[mat[xc][xy]] = 0;
- q.emplace(mat[xc][xy]);
- while (!q.empty) {
- int node = q.front();
- state.set(node);
- for (const auto &son : graph[node]) {
- if (!state[son]) {
- state.set(son);
- road[son] = road[node] + 1;
- q.emplace(son);
- }
- }
- }
- for (const auto &i : galeries) {
- if (min_dist > road[i.first]) {
- min_dist = road[i.first];
- min_line = i.start_x;
- min_column = i.start_y;
- }
- if (min_dist > road[i.second]) {
- min_dist = road[i.second];
- min_line = i.end_x;
- min_column = i.end_y;
- }
- }
- }
- void write() {
- ofstream fout("cartite.out");
- if (p == 1) {
- bfs();
- fout << min_line << ' ' << min_column << ' ' << min_dist;
- } else {
- }
- fout.close();
- }
- int main() {
- read();
- write();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement