Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <algorithm>
- #include <stdlib.h>
- #include <vector>
- #include <queue>
- using namespace std;
- struct vertex {
- int i1, j1, i2, j2, range, id;
- } S, to;
- vector <vector<int>> A, B;
- vector <bool> used;
- queue <vertex> q;
- int N, R1, C1, R2, C2;
- int N2, N3, N4, range = 0;
- void input() {
- ifstream fin("input.txt");
- fin >> N >> R1 >> C1 >> R2 >> C2;
- S.i1 = R1;
- S.j1 = C1;
- S.i2 = R2;
- S.j2 = C2;
- S.range = 0;
- N2 = N*N;
- N3 = N2*N;
- N4 = N3*N;
- A.resize(N);
- B.resize(N);
- int temp;
- for (int i = 0; i < N; i++) {
- A[i].reserve(N);
- for (int j = 0; j < N; j++) {
- fin >> temp;
- A[i].push_back(temp);
- }
- }
- for (int i = 0; i < N; i++) {
- B[i].reserve(N);
- for (int j = 0; j < N; j++) {
- fin >> temp;
- B[i].push_back(temp);
- }
- }
- fin.close();
- }
- void output(int x) {
- ofstream fout("output.txt");
- fout << x;
- fout.close();
- }
- bool check(vector <vector<int>> &lab, int i, int j) {
- if (i >= 0 && j >= 0 && i < N && j < N && lab[i][j] == 0)
- return true;
- else
- return false;
- }
- int identify(vertex &v) {
- return v.i1*N3 + v.j1*N2 + v.i2*N + v.j2;
- }
- void step_up(vertex &v) {
- to = v;
- if (check(A, to.i1 - 1, to.j1)) {
- to.i1 -= 1;
- }
- if (check(B, to.i2 - 1, to.j2)) {
- to.i2 -= 1;
- }
- to.id = identify(to);
- to.range++;
- if (to.id == 0) {
- output(to.range);
- exit(EXIT_SUCCESS);
- }
- if (!used[to.id]) {
- used[to.id] = true;
- q.push(to);
- }
- }
- void step_down(vertex &v) {
- to = v;
- if (check(A, to.i1 + 1, to.j1)) {
- to.i1 += 1;
- }
- if (check(B, to. i2 + 1, to.j2)) {
- to.i2 += 1;
- }
- to.id = identify(to);
- to.range++;
- if (to.id == 0) {
- output(to.range);
- exit(EXIT_SUCCESS);
- }
- if (!used[to.id]) {
- used[to.id] = true;
- q.push(to);
- }
- }
- void step_right(vertex &v) {
- to = v;
- if (check(A, to. i1, to.j1 + 1)) {
- to.j1 += 1;
- }
- if (check(B, to.i2, to.j2 + 1)) {
- to.j2 += 1;
- }
- to.id = identify(to);
- to.range++;
- if (to.id == 0) {
- output(to.range);
- exit(EXIT_SUCCESS);
- }
- if (!used[to.id]) {
- used[to.id] = true;
- q.push(to);
- }
- }
- void step_left(vertex &v) {
- to = v;
- if (check(A, to. i1, to.j1 - 1)) {
- to.j1 -= 1;
- }
- if (check(B, to.i2, to.j2 - 1)) {
- to.j2 -= 1;
- }
- to.id = identify(to);
- to.range++;
- if (to.id == 0) {
- output(to.range);
- exit(EXIT_SUCCESS);
- }
- if (!used[to.id]) {
- used[to.id] = true;
- q.push(to);
- }
- }
- void bfs() {
- used.resize(N4);
- S.id = S.i1*N3 + S.j1*N2 + S.i2*N + S.j2;
- used[S.id] = true;
- q.push(S);
- int result = -1;
- while (!q.empty()) {
- vertex v = q.front();
- q.pop();
- // if (check(A, v.i1 - 1, v.j1) && check(A, v.i2 - 1, v.j2) && !used[identify(v) - N3 - N])
- step_up(v);
- // if (check(A, v.i1 + 1, v.j1) && check(A, v.i2 + 1, v.j2) && !used[identify(v) + N3 + N])
- step_down(v);
- // if (check(A, v.i1, v.j1 - 1) && check(A, v.i2, v.j2 - 1) && !used[identify(v) - N2 - 1])
- step_left(v);
- // if (check(A, v.i1, v.j1 + 1) && check(A, v.i2, v.j2 + 1) && !used[identify(v) + N2 + 1])
- step_right(v);
- }
- }
- int main() {
- input();
- bfs();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement