/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Point {
    int x;
    int y;
    Point(int x, int y) : x(x), y(y) {}
};

bool InMap(const vector<vector<int>>& map, const Point& p) {
    return (p.x >= 0 && p.x < map.size() && p.y >= 0 && p.y < map[0].size());
}

void PrintMap(const vector<vector<int>>& map) {
    for (int i = 0; i < map.size(); ++i) {
        for (int j = 0; j < map[0].size(); ++j) {
            std::cout << map[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

bool PathExists(const vector<vector<int>>& map, const Point& ini_pos, const Point& fin_pos, int& len_path, const int neighboring  = 4) {

    vector<vector<int>> dist_map(map.size(), vector<int> (map[0].size(), -1));
    dist_map[ini_pos.x][ini_pos.y] = 0;

    vector<vector<int>> neighbors_map;
    if (neighboring == 4) {
        neighbors_map = {{-1, 0},
                        {1, 0},
                        {0, -1},
                        {0, 1}};
    }
    else {
        neighbors_map = {{-1, 0},
                        {-1, 1},
                        {-1, -1},
                        {1, -1},
                        {1, 0},
                        {1, 1},
                        {0, -1},
                        {0, 1}};
    }

    queue<Point> qPoints;
    qPoints.push(ini_pos);
    int dist = 1;

    while (!qPoints.empty()) {

        int nPoints = qPoints.size ();

        while (nPoints > 0) {
            Point current = qPoints.front();
            qPoints.pop();

            for (int i = 0; i < neighboring; ++i) {
                Point p = Point(current.x + neighbors_map[i][0], current.y + neighbors_map[i][1]);
                if (InMap(map, p) && map[p.x][p.y] == 0 && dist_map[p.x][p.y] == -1) {
                    qPoints.push(p);
                    dist_map[p.x][p.y] = dist;
                }
            }
            nPoints--;
        }
        ++dist;
    }

    PrintMap(dist_map);

    len_path = dist_map[fin_pos.x][fin_pos.y];

    return (dist_map[fin_pos.x][fin_pos.y] != -1);
}


int main()
{
    vector<vector<int>> map = {{0, 0, 0, 0, 1, 0},
                            {0, 0, 0, 0, 1, 0},
                            {0, 0, 0, 1, 1, 0},
                            {0, 0, 0, 0, 0, 0},
                            {0, 1, 1, 0, 1, 0}};

    Point ini_pos(0, 0);
    Point fin_pos(2, 5);

    PrintMap(map);

    std::cout << std::endl;

    int len_path = 0;

    bool path_exists = PathExists(map, ini_pos, fin_pos, len_path, 4);

    std::cout << path_exists << std::endl;

    std::cout << "Path length: " << len_path << std::endl;

    return 0;
}