#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <queue>

using namespace std;

void bfs(const vector<vector<int>> &map,
         int startPoint,
         std::vector<std::pair<int, int>> &pointsOfInterest,
         int N,
         int M,
         vector<vector<int>> &outDistances) {

  // all the ones left to visit
  std::queue<std::pair<int, int>> toVisit;
  toVisit.emplace(pointsOfInterest[startPoint]);

  // all the nodes that we have visited
  std::vector<bool> visited;
  visited.resize(N * M, false);

  // all the nodes that we have added
  std::vector<bool> added;
  added.resize(N * M, false);

  // distances
  std::vector<int> distances;
  distances.resize(N * M, 0);

  while(!toVisit.empty()) {

    // get the stuff to visit
    int i = toVisit.front().first;
    int j = toVisit.front().second;
    toVisit.pop();

    // mark as visited
    visited[i * M + j] = true;

    if(i + 1 < N && !visited[(i + 1) * M + j] && map[i + 1][j] != 1 && !added[(i + 1) * M + j]) {
      toVisit.push(std::make_pair(i+1, j));
      distances[(i + 1) * M + j] = distances[i * M + j] + 1;
      added[(i + 1) * M + j] = true;
    }

    if(i - 1 >= 0 && !visited[(i - 1) * M + j] && map[i - 1][j] != 1 && !added[(i - 1) * M + j]) {
      toVisit.push(std::make_pair(i - 1, j));
      distances[(i - 1) * M + j] = distances[i * M + j] + 1;
      added[(i - 1) * M + j] = true;
    }

    if(j + 1 < M && !visited[i * M + j + 1] && map[i][j + 1] != 1 && !added[i * M + j + 1]) {
      toVisit.push(std::make_pair(i, j + 1));
      distances[i * M + j + 1] = distances[i * M + j] + 1;
      added[i * M + j + 1] = true;
    }

    if(j - 1 >= 0 && !visited[i * M + j - 1] && map[i][j - 1] != 1 && !added[i* M + j - 1]) {
      toVisit.push(std::make_pair(i, j - 1));
      distances[i * M + j - 1] = distances[i * M + j] + 1;
      added[i * M + j - 1] = true;
    }
  }

  // set the output distances
  for(int i = 0; i < pointsOfInterest.size(); ++i) {
    if(visited[pointsOfInterest[i].first * M + pointsOfInterest[i].second]) {
      outDistances[startPoint][i] = distances[pointsOfInterest[i].first * M + pointsOfInterest[i].second];
    }
  }
}

int findDistance(const vector<vector<int>> &map, int x, int y) {

  int N = map.size();
  int M = map[0].size();

  std::vector<std::pair<int, int>> toVisit = {{0, 0}};
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) {

      // check if it is start or end
      bool isEnd = i == x && j == y;
      bool isStart = i == 0 && j == 0;

      if(map[i][j] == 2 && !isStart && !isEnd) {
        toVisit.emplace_back(i, j);
      }
    }
  }
  toVisit.emplace_back(x, y);

  // init the distances to -1
  vector<vector<int>> distances;
  distances.resize(toVisit.size());
  for(auto &d : distances) {
    d.resize(toVisit.size(), -1);
  }

  // go through all the nodes we need to visit
  for(int i = 0; i < toVisit.size(); ++i) {
    bfs(map, i, toVisit, N, M, distances);
  }

  // if one of them can not be reached from the source return -1
  for(int i = 0; i < toVisit.size(); ++i) {
    if(distances[0][i] == -1) {
      return -1;
    }
  }

  // check all permutations
  std::vector<int> permutation;
  permutation.reserve(toVisit.size());
  for(int i = 1; i < toVisit.size() - 1; ++i) {
    permutation.emplace_back(i);
  }

  // if we don't have anything just return
  if(permutation.empty()) {
    return distances[0][toVisit.size() - 1];
  }

  // figure out the minimum distance
  int minDist = std::numeric_limits<int>::max();
  do {

    // distance to the first in the permutation
    int dist = distances[0][permutation.front()];

    // sum up the distance
    for(int i = 0; i < permutation.size() - 1; ++i) {
      dist += distances[i][i + 1];
    }

    // distance from the last in the permutation
    dist += distances[permutation.back()][toVisit.size() - 1];

    // figure out the minimum distance
    minDist = std::min(minDist, dist);

  } while (std::next_permutation(permutation.begin(), permutation.end()) );

  return minDist;
}



int main() {

  // init the distances to -1
  vector<vector<int>> map;
  map.resize(100);
  for(auto &d : map) {
    d.resize(100, 0);
  }

  //for(int i = 0; i < 10; i++) {
  //  map[i * 10][i * 10] = 2;
  //}


  //std::cout << findDistance(map, 99, 99);
  std::cout << findDistance({{0, 0, 0, 0, 1},
                             {1, 1, 1, 0, 0},
                             {1, 1, 2, 1, 0},
                             {1, 1, 1, 1, 2}}, 3, 4);

  return 0;
}