Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "pch.h"
- #include <iostream>
- #include <fstream>
- #include <queue>
- using namespace std;
- #define DIMEN 10
- #define POSIT 4
- ifstream in("date.in");
- ofstream out("date.out");
- int n, m, matrice[DIMEN][DIMEN], matriceLee[DIMEN][DIMEN];
- int startx, starty, stopx, stopy;
- int di[POSIT] = { 0, 0, -1, 1 };
- int dj[POSIT] = { -1, 1, 0, 0 };
- queue < pair < int, int > > Coada;
- struct {
- int x, y;
- }stiva[DIMEN * DIMEN];
- int k = 0;
- void Citire();
- void Afisare();
- bool e_ok(int i, int j);
- void agl_Lee();
- void Drum_Optim();
- int main() {
- Citire();
- agl_Lee();
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++)
- cout << matriceLee[i][j] << " ";
- cout << endl;
- }
- Drum_Optim();
- return 0;
- }
- void Citire() {
- in >> n >> m;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++)
- in >> matrice[i][j];
- in >> startx >> starty;
- in >> stopx >> stopy;
- in.close();
- }
- void Afisare() {
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- cout << matrice[i][j] << " ";
- out << matrice[i][j] << " ";
- }
- cout << endl;
- out << '\n';
- }
- out.close();
- }
- bool e_ok(int i, int j) {
- if (matrice[i][j] == -1) return false;
- if (i < 0 || j < 0 || i >= n || j >= m) return false;
- return true;
- }
- void agl_Lee() {
- int i, j, i_urm, j_urm;
- matriceLee[startx][starty] = 1;
- Coada.push(make_pair(startx, starty));
- while (!Coada.empty()) {
- i = Coada.front().first;
- j = Coada.front().second;
- Coada.pop();
- for (int d = 0; d < POSIT; d++) {
- i_urm = i + di[d];
- j_urm = j + dj[d];
- if (e_ok(i_urm, j_urm) && matriceLee[i_urm][j_urm] == 0) {
- matriceLee[i_urm][j_urm] = matriceLee[i][j] + 1;
- Coada.push(make_pair(i_urm, j_urm));
- }
- }
- }
- }
- void Drum_Optim() {
- int i = stopx, j = stopy;
- stiva[k].x = i;
- stiva[k].y = j;
- k++;
- while (matriceLee[i][j] > 1) {
- for (int d = 0; d < POSIT; d++) {
- int i_urm = i + di[d];
- int j_urm = j + dj[d];
- if (matriceLee[i_urm][j_urm] == matriceLee[i][j] - 1) {
- stiva[k].x = i;
- stiva[k].y = j;
- k++;
- i = i_urm;
- j = j_urm;
- break;
- }
- }
- }
- k--;
- while (k >= 0) {
- out << stiva[k].x << " " << stiva[k].y << '\n';
- k--;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment