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 <map>
- #include <queue>
- using namespace std;
- vector <vector<int>> A, B;
- int N, R1, C1, R2, C2;
- int N2, N3, N4;
- bool finish = false;
- struct vertex {
- int x1, y1, x2, y2, range, id;
- } S;
- void input() {
- ifstream fin("input1.txt");
- fin >> N >> R1 >> C1 >> R2 >> C2;
- S.x1 = R1; // строка 1
- S.y1 = C1; // столбец 1
- S.x2 = R2; // строка 2
- S.y2 = C2; // столбец 2
- 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();
- }
- int range = 0;
- bool f = false;
- vertex to;
- vector <bool> used;
- queue <vertex> q;
- void step_up(vertex v) {
- f = false;
- to.x1 = to.y1 = to.x2 = to.y2 = to.id = to.range = -1;
- if (v.x1 - 1 >= 0) {
- f = true;
- if (A[v.x1 - 1][v.y1] == 0) {
- to.x1 = v.x1 - 1;
- to.y1 = v.y1;
- to.id = (v.x1 - 1)*N3 + v.y1*N2;
- }
- else {
- to.x1 = v.x1;
- to.y1 = v.y1;
- to.id = v.x1*N3 + v.y1*N2;
- }
- }
- if (v.x2 - 1 >= 0) {
- f = true;
- if (B[v.x2 - 1][v.y2] == 0) {
- to.x2 = v.x2 - 1;
- to.y2 = v.y2;
- to.id += (v.x2 - 1)*N + v.y2;
- }
- else {
- to.x2 = v.x2;
- to.y2 = v.y2;
- to.id += v.x2*N + v.y2;
- }
- }
- if (to.x1 == 0 && to.y1 == 0 && to.x2 == 0 && to.y2 == 0) {
- finish = true;
- v.range = range;
- }
- if (f && !used[to.id]) {
- used[to.id] = true;
- to.range = range;
- q.push(to);
- }
- }
- void step_down(vertex v) {
- f = false;
- to.x1 = to.y1 = to.x2 = to.y2 = to.id = to.range = -1;
- if (v.x1 + 1 < N) {
- f = true;
- if (A[v.x1 + 1][v.y1] == 0) {
- to.x1 = v.x1 + 1;
- to.y1 = v.y1;
- to.id = (v.x1 + 1)*N3 + v.y1*N2;
- }
- else {
- to.x1 = v.x1;
- to.y1 = v.y1;
- to.id = v.x1*N3 + v.y1*N2;
- }
- }
- if (v.x2 + 1 < N) {
- f = true;
- if (B[v.x2 + 1][v.y2] == 0) {
- to.x2 = v.x2 + 1;
- to.y2 = v.y2;
- to.id += (v.x2 + 1)*N + v.y2;
- }
- else {
- to.x2 = v.x2;
- to.y2 = v.y2;
- to.id += v.x2*N + v.y2;
- }
- }
- if (to.x1 == 0 && to.y1 == 0 && to.x2 == 0 && to.y2 == 0) {
- finish = true;
- v.range = range;
- }
- if (f && !used[to.id]) {
- used[to.id] = true;
- to.range = range;
- q.push(to);
- }
- }
- void step_right(vertex v) {
- f = false;
- to.x1 = to.y1 = to.x2 = to.y2 = to.id = to.range = -1;
- if (v.y1 + 1 < N) {
- f = true;
- if (A[v.x1][v.y1 + 1] == 0) {
- to.x1 = v.x1;
- to.y1 = v.y1 + 1;
- to.id = v.x1*N3 + (v.y1 + 1)*N2;
- }
- else {
- to.x1 = v.x1;
- to.y1 = v.y1;
- to.id = v.x1*N3 + v.y1*N2;
- }
- }
- if (v.y2 + 1 < N) {
- f = true;
- if (B[v.x2][v.y2 + 1] == 0) {
- to.x2 = v.x2;
- to.y2 = v.y2 + 1;
- to.id += v.x2*N + (v.y2 + 1);
- }
- else {
- to.x2 = v.x2;
- to.y2 = v.y2;
- to.id += v.x2*N + v.y2;
- }
- }
- if (to.x1 == 0 && to.y1 == 0 && to.x2 == 0 && to.y2 == 0) {
- finish = true;
- v.range = range;
- }
- if (f && !used[to.id]) {
- used[to.id] = true;
- to.range = range;
- q.push(to);
- }
- }
- void step_left(vertex v) {
- f = false;
- to.x1 = to.y1 = to.x2 = to.y2 = to.id = to.range = -1;
- if (v.y1 - 1 >= 0) {
- f = true;
- if (A[v.x1][v.y1 - 1] == 0) {
- to.x1 = v.x1;
- to.y1 = v.y1 - 1;
- to.id = v.x1*N + (v.y1 - 1)*N2;
- }
- else {
- to.x1 = v.x1;
- to.y1 = v.y1;
- to.id = v.x1*N3 + v.y1*N2;
- }
- }
- if (v.y2 - 1 >= 0) {
- f = true;
- if (B[v.x2][v.y2 - 1] == 0) {
- to.x2 = v.x2;
- to.y2 = v.y2 - 1;
- to.id += v.x2*N + (v.y2 - 1);
- }
- else {
- to.x2 = v.x2;
- to.y2 = v.y2;
- to.id += v.x2*N + v.y2;
- }
- }
- if (to.x1 == 0 && to.y1 == 0 && to.x2 == 0 && to.y2 == 0) {
- finish = true;
- v.range = range;
- }
- if (f && !used[to.id]) {
- used[to.id] = true;
- to.range = range;
- q.push(to);
- }
- }
- int bfs() {
- used.resize(N4);
- S.id = S.x1*N3 + S.y1*N2 + S.x2*N + S.y2;
- used[S.id] = true;
- q.push(S);
- while (!q.empty()) {
- vertex v = q.front();
- q.pop();
- range++;
- step_up(v);
- if (finish)
- return v.range + 1;
- step_down(v);
- if (finish)
- return v.range + 1;
- step_left(v);
- if (finish)
- return v.range + 1;
- step_right(v);
- if (finish)
- return v.range + 1;
- }
- }
- void output(int x) {
- ofstream fout("output.txt");
- fout << x;
- fout.close();
- }
- int main() {
- input();
- int result = bfs();
- output(result);
- cout << result << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement