// Example program
#include <iostream>
#include <cstring>

using namespace std;

// Размеры лабиринта
const int WIDTH = 7;
const int HEIGHT = 7;


// Массив лабиринта 0 - свободно, 1 - стена
char labirint[WIDTH][HEIGHT] = {
    {'0','0','0','0','0','1','0'},
    {'0','1','1','1','0','1','0'},
    {'0','0','0','1','1','1','1'},
    {'0','1','0','0','0','0','0'},
    {'1','1','1','1','0','0','0'},
    {'0','0','0','0','0','1','0'},
    {'0','0','0','0','0','1','0'},

};


// Точки финиша и старта
int start[2] = {0,0};
int finish[2] = {WIDTH-1,HEIGHT-1};


// Функция проверяющая, находится ли точка внутри лабиринта
bool isExist(int row, int column){
    if(row >= 0 && row < HEIGHT && column >= 0 && column < WIDTH){
        return true;
    } else {
        return false;
    }
};


// Данные о том, за какое минимальное кол-во шагов можно попасть в клетку [i,j]
int info_steps[WIDTH][HEIGHT];

// Выводит информацию о поле (сколько нужно шагов до каждой клетки)
void printData(){
    for(int i = 0; i<HEIGHT; i++){
        cout << endl;
        for(int j = 0; j<WIDTH; j++){
            // Устанавливаем ширину выводимого потока (3 символа) для цифр и знака минус
            cout.width(3);
            cout << info_steps[i][j] << " ";
        }
    }

    cout << endl << endl;
};

// Распечатать лабиринт
void printLabirint(){
    for(int i = 0; i<HEIGHT; i++){
        cout << endl;
        for(int j = 0; j<WIDTH; j++){
            // Устанавливаем ширину выводимого потока (3 символа) для цифр и знака минус
            cout.width(1);
            cout << labirint[i][j] << " ";
        }
    }

    cout << endl << endl;
};

// Распечатать путь
void printPath(){
  // Шаги, за которое можно добраться от начала до финиша
  int steps = info_steps[finish[0]][finish[1]];

  // Берём финишную точку и начинаем высчитывать путь
  int point[2] = {finish[0], finish[1]};

  // Чем будем помечать путь
  char mark = '*';

  // Помечаем её
  labirint[point[0]][point[1]] = mark;


  for(int s = steps; s>0; s--){

    // Проверяем, существует ли точка сверху
    if(isExist(point[0]-1, point[1])){
      // Можно ли добраться в эту точку сверху?
      if(info_steps[point[0]-1][point[1]] == s-1){
        labirint[point[0]-1][point[1]] = mark;
        // Берём эту точку как текущую
        point[0] = point[0]-1;
        point[1] = point[1];
        continue;
      }
    }

    // Проверяем, существует ли точка снизу
    if(isExist(point[0]+1, point[1])){
      // Можно ли добраться в эту точку сверху?
      if(info_steps[point[0]+1][point[1]] == s-1){
        labirint[point[0]+1][point[1]] = mark;
        // Берём эту точку как текущую
        point[0] = point[0]+1;
        point[1] = point[1];
        continue;
      }
    }

    // Проверяем, существует ли точка слева
    if(isExist(point[0], point[1]-1)){
      // Можно ли добраться в эту точку сверху?
      if(info_steps[point[0]][point[1]-1] == s-1){
        labirint[point[0]][point[1]-1] = mark;
        // Берём эту точку как текущую
        point[0] = point[0];
        point[1] = point[1]-1;
        continue;
      }
    }

    // Проверяем, существует ли точка справа
    if(isExist(point[0], point[1]+1)){
      // Можно ли добраться в эту точку сверху?
      if(info_steps[point[0]][point[1]+1] == s-1){
        labirint[point[0]][point[1]+1] = mark;
        // Берём эту точку как текущую
        point[0] = point[0];
        point[1] = point[1]+1;
        continue;
      }
    }

  }

  // Выводим лабиринт с путём
  printLabirint();

}


int main()
{

    // Выводим лабиринт
    printLabirint();

    // Заполняем data -1
    for(int i = 0; i<HEIGHT; i++){
        for(int j = 0; j<WIDTH;j++){
            info_steps[i][j] = -1;
        }
    }



    // Массив из новых точек
    int points[WIDTH*HEIGHT][2];
    int points_count = 0;

    // Добавляем точку старта
    points[points_count][0] = start[0];
    points[points_count][1] = start[1];
    points_count++;



    // Пока searching == true - ищем
    bool searching = true;
    int iter = 0;
    while(searching){

        // Массив точек, полученных на этой итерации
        int points_new[WIDTH*HEIGHT][2];
        int points_new_count = 0;

        // Проходимся по всем точкам
        for(int i = 0; i<points_count; i++){

            // Строка и колонка лабиринта
            int row = points[i][0];
            int column = points[i][1];

            // Ставим минимальное количество шагов для точки
            info_steps[row][column] = iter;


            // Проверка конца лабиринта
            if(row == finish[0] && column == finish[1]){
              cout << "Path was found!" << endl;
              printData();
              printPath();
              searching = false;
              break;
            }


            // Проверяем выше точки
            if(isExist(row-1, column)){
                // В данной точке не стена
                if(labirint[row-1][column] == '0'){
                    // Мы ещё не были в данной точке
                    if(info_steps[row-1][column] == -1){
                        points_new[points_new_count][0] = row-1;
                        points_new[points_new_count][1] = column;
                        points_new_count++;
                    }
                }
            }

            // Проверяем ниже точки
            if(isExist(row+1, column)){
                // В данной точке не стена
                if(labirint[row+1][column] == '0'){
                    // Мы ещё не были в данной точке
                    if(info_steps[row+1][column] == -1){
                        points_new[points_new_count][0] = row+1;
                        points_new[points_new_count][1] = column;
                        points_new_count++;
                    }
                    }
            }

            // Проверяем правее точки
            if(isExist(row, column+1)){
                // В данной точке не стена
                if(labirint[row][column+1] == '0'){
                    // Мы ещё не были в данной точке
                    if(info_steps[row][column+1] == -1){
                        points_new[points_new_count][0] = row;
                        points_new[points_new_count][1] = column+1;
                        points_new_count++;
                    }
                }
            }

            // Проверяем левее точки
            if(isExist(row, column-1) ){
                // В данной точке не стена
                if(labirint[row][column-1] == '0'){
                    // Мы ещё не были в данной точке
                    if(info_steps[row][column-1] == -1){
                        points_new[points_new_count][0] = row;
                        points_new[points_new_count][1] = column-1;
                        points_new_count++;
                    }
                }
            }
        }



        // Записываем данные новых найденных точек в общий массив точек
        // Для их проверки на следующем шаге
        points_count = points_new_count;
        memcpy(&points[0], &points_new[0], sizeof(int)*2*points_new_count);

        // Если везде тупики
        if(points_new_count == 0){
          cout << "No path!" << endl;
          searching = false;
          break;
        }


        // Делаем шаг дальше
        iter++;
        if(iter >= 25){
            break;
        }
    }

    // Остановка экрана
    cin.get();
}