Lee1

#include <bits/stdc++.h>

using namespace std;

ifstream fin ("lee1.in");
ofstream fout ("lee1.out");
int dl[4] = {0, 0, -1, 1};
int dc[4] = {1, -1, 0, 0};
int n, x[10], y[10], dist[10][10], yeet1, yeet2, p[10], m, d[102][102], sol[10], k;
bool v[102][102];

bool ok (int i, int j) {
  if (i >= 1 && i <= n && j >= 1 && j <= m)
    return 1;
  return 0;
}

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      fin >> v[i][j];
  fin >> x[1] >> y[1] >> yeet1 >> yeet2;
  fin >> k;
  x[k + 2] = yeet1; y[k + 2] = yeet2;
  for(int i = 2; i <= k + 1; i++)
    fin >> x[i] >> y[i];
  for (int i = 1; i <= k + 2; i++) {
    memset(d, 0, sizeof(d));
    queue<pair<int, int> >q;
    q.push({x[i], y[i]});
    while (!q.empty()) {
      int x1 = q.front().first, y1 = q.front().second;
      q.pop();
      for (int k = 0; k < 4; k++) {
        int ii = x1 + dl[k];
        int jj = y1 + dc[k];
        if (!v[ii][jj] && !d[ii][jj] && (ii != x[i] || jj != y[i]) && ok(ii, jj)) {
          q.push({ii, jj});
          d[ii][jj] = d[x1][y1] + 1;;
        }
      }
    }
    for (int j = 1; j <= k + 2; j++)
      if (i != j)
        dist[i][j] = d[x[j]][y[j]];
  }
  for (int i = 1; i <= k; i++)
    p[i] = i + 1;
  int mn = 1e9;
  do {
    int aux = dist[1][p[1]];
    for (int i = 1; i < k; i++)
      aux += dist[p[i]][p[i + 1]];
    aux += dist[p[k]][k + 2];
    if (aux  < mn) {
      for (int i = 1; i <= k; i++)
        sol[i] = p[i];
      mn = aux;
    }
    else if (aux == mn){
      bool ok;
      for (int i = 1; i <= k; i++) {
        if (x[p[i]] == x[sol[i]]) {
          if (y[p[i]] < y[sol[i]]) {
            ok = 1;
            break;
          }
          else {
            ok = 0;
            break;
          }
        }
        else if (x[p[i]] < x[sol[i]]) {
          ok = 1;
          break;
        }
        else if (x[p[i]] > x[sol[i]]) {
          ok = 0;
          break;
        }
      }
      if (ok)
        for (int i = 1; i <= k; i++)
          sol[i] = p[i];
    }

  }while (next_permutation(p + 1, p + k + 1));
  fout << mn << "\n";
  fout << x[1] << "," << y[1] << "\n";
  for (int i = 1; i <= k; i++)
    fout << x[sol[i]] << "," << y[sol[i]] << "\n";
  fout << x[k + 2] << "," << y[k + 2] << "\n";
  return 0;
}