Поиск пути

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <fstream>
 
typedef std::vector<std::pair<char, std::pair<int, std::pair<int, int> > > > VectorOfPairs;
 
static const int mx = 9, my = 9;
static const int N = 8, M = 11;
static bool findWay = false;
 
struct MyClass{
    char _symbol;
    int _value_of_wave;
    int _parent_x;
    int _parent_y;
 
    MyClass(char symbol = ' ', int value_of_wave = 0, int parent_x = 0, int parent_y = 0) 
        : _symbol(symbol), _value_of_wave(value_of_wave), _parent_x(parent_x), _parent_y(parent_y)
    {}
};
 
void DoWater(std::vector<VectorOfPairs>& matr, int y, int x, int& cnt){
    int empty = 0;
    //верхняя клетка
    if ((y - 1) > -1) 
        //проверка клетки на наличие конца
        if (matr[y - 1][x].second.first == -1){
            std::cout << "We find end!" << std::endl;
            ::findWay = true;
            //запоминание координат клетки родителя волны
            matr[y - 1][x].second.second.first = y;
            matr[y - 1][x].second.second.second = x;
        }else 
            //заполнение клетки водой
            if (matr[y - 1][x].second.first == empty){
                matr[y - 1][x].second.first = cnt + 1;
                //запоминание координат клетки родителя волны
                matr[y - 1][x].second.second.first = y;
                matr[y - 1][x].second.second.second = x;
            }
    //правая клетка
    if ((x + 1) < ::M)
        //проверка клетки на наличие конца
        if (matr[y][x + 1].second.first == -1){
            std::cout << "We find end!" << std::endl;
            ::findWay = true;
            //запоминание координат клетки родителя волны
            matr[y][x + 1].second.second.first = y;
            matr[y][x + 1].second.second.second = x;
        }else 
            //заполнение клетки водой
            if (matr[y][x + 1].second.first == empty){
                matr[y][x + 1].second.first = cnt + 1;
                //запоминание координат клетки родителя волны
                matr[y][x + 1].second.second.first = y;
                matr[y][x + 1].second.second.second = x;
            }
    //нижняя клетка
    if ((y + 1) < ::N)
        //проверка клетки на наличие конца
        if (matr[y + 1][x].second.first == -1){
            std::cout << "We find end!" << std::endl;
            ::findWay = true;
            //запоминание координат клетки родителя волны
            matr[y + 1][x].second.second.first = y;
            matr[y + 1][x].second.second.second = x;
        }else 
            //заполнение клетки водой
            if (matr[y + 1][x].second.first == empty){
                matr[y + 1][x].second.first = cnt + 1;
                //запоминание координат клетки родителя волны
                matr[y + 1][x].second.second.first = y;
                matr[y + 1][x].second.second.second = x;
              }
    //левая клетка
    if ((x - 1) > -1)
        //проверка клетки на наличие конца
        if (matr[y][x - 1].second.first == -1){
            std::cout << "We find end!" << std::endl;
            ::findWay = true;
            //запоминание координат клетки родителя волны
            matr[y][x - 1].second.second.first = y;
            matr[y][x - 1].second.second.second = x;
        }else 
            //заполнение клетки водой
            if (matr[y][x - 1].second.first == empty){
                matr[y][x - 1].second.first = cnt + 1;
                //запоминание координат клетки родителя волны
                matr[y][x - 1].second.second.first = y;
                matr[y][x - 1].second.second.second = x;
              }
}
 
void main()
{
    int begin_i = 0, begin_j = 0, //координаты входа
        end_i = 0, end_j = 0, //координыта выхода
        count = 1;
    bool noDoWater = false; //досрочное окончание поиска конца, если не было волны
    std::vector<VectorOfPairs> arr(N, VectorOfPairs(M));
 
    std::ifstream infile("C:\Labirint.txt");
//считывание лабиринта в массив
    if(!infile){
        std::cout << "Error";
        exit(1);
    }
    for (int i = 0; i < N; ++i){
        for (int j = 0; j < M; ++j){
            infile.get(arr[i][j].first);
            if (arr[i][j].first == '@'){
                begin_i = i;
                begin_j = j;
                arr[i][j].second.first = 1;
                //запоминание начала координат старта
                arr[i][j].second.second.first = i;
                arr[i][j].second.second.second = j;
            }
            if (arr[i][j].first == '$'){
                end_i = i;
                end_j = j;
                arr[i][j].second.first = -1;
            }
            if (arr[i][j].first == '+'){
                arr[i][j].second.first = -2;
            }
        }
    }
 
//поиск пути
 
    int cnt = 1, //счетчик номера волны
        size_y = 0, size_x = 0, //размеры поля в кт. ищем нужный номер волны
        move_y = begin_i, move_x = begin_j, //начальные координаты квадрата в кт. производим поиск волны
        empty = 0; //условное обозначение пустой клетки
    do{
        noDoWater = true;
        //просмотр определенного участка поля и заполнение новых клеток водой
        for (int i = move_y; i <= (move_y + size_y); ++i)
            for (int j = move_x; j <= (move_x + size_x); ++j){
                if (arr[i][j].second.first == cnt){
                    DoWater(arr, i, j, cnt);
                    noDoWater = false;
                }
            }
        //изменение поля в кт. произойдет заполнение новых клеток водой
        //изменения начальных координат участка поля в кт. будет происходить поиск последней волны
        if (move_y > 0)
            --move_y;
        if (move_x > 0)
            --move_x;
        //изменение размеров поля
        if((move_y + size_y + 2) <= (N - 1))
            size_y += 2;
        if((move_x + size_x + 2) <= (M - 1))
            size_x += 2;
        ++cnt;
    }while((!noDoWater) && (!::findWay));
//вывод результата
    if(noDoWater)
        std::cout << "No way found" <<std::endl;
    else{
        int prev_y = 0, temp_y = end_i, prev_x = 0, temp_x = end_j;
        do{
            prev_y = temp_y;
            prev_x = temp_x;
            std::cout << prev_y << ' ' << prev_x << std::endl;
            if ((arr[prev_y][prev_x].first != '@') && (arr[prev_y][prev_x].first != '$'))
                arr[prev_y][prev_x].first = '*';
            temp_y = arr[prev_y][prev_x].second.second.first;
            temp_x = arr[prev_y][prev_x].second.second.second;
        }while((prev_y != begin_i) || (prev_x != begin_j));
    }
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            std::cout << arr[i][j].first;
 
    std::cout << std::endl;
}