Rank 11/80

アプローチ stitch の数が多いとき:
  1. cross stitch 単位で、任意の cross stitch からの距離が0の imaginary cross stitch を加えて Travelling Salesman Problem として解く。
  2. 直前の cross stitch と次の cross stitch からの距離が短い縫い方を貪欲法で見つける。
  3. 2opt で改善する。
stitch の数が少ないとき:
  1. stitch 単位で、任意の stitch からの距離が0の imaginary stitch を加えて、 Travelling Salesman Problem として解く。

Approach(Google Translate) When the number of stitches is large:

  1. In cross stitch unit, add imaginary cross stitch with distance 0 from arbitrary cross stitch and solve it as Traveling Salesman Problem.
  2. Find greedy how to sew a short distance from the previous cross stitch and the next cross stitch.
  3. Improve by 2opt.

When the number of stitches is small:

  1. Add imaginary stitch with distance 0 from arbitrary stitch in stitch unit and solve it as Traveling Salesman Problem.


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

public class CrossStitch {
private double lengthFront;
private double lengthBack;

private int S;
private Watch watch = new Watch();
private HashMap<Integer, ArrayList<Point>> colorToPoints = new HashMap<>();
private HashMap<Integer, ArrayList<Stitch>> colorToStitches = new HashMap<>();

private int numStitches;
private XorShift xorShift = new XorShift(System.nanoTime());
private double[][] distancesStitchTo4PointOfStitch;
private int[] index2stitch;
private int[] stitch2index;
private IntArray[] stitch2nearestStitches;
private boolean[] startFromUpper;
private HashMap<Integer, HashMap<Integer, Integer>> stitch2nearestStitchIndex2index;

private int sumLoops;
private int sumTries;
private int sumAccepts;
private ArrayList<Stitch> stitches;

public String[] embroider(String[] pattern) {
init(pattern);

ArrayList<String> ret = new ArrayList<>();

double initTime = watch.getSecond();

double eachColorTime = (1 * 9.5 - initTime) / colorToPoints.keySet().size();

double sumBackLength = 0;

for (Integer color : colorToPoints.keySet()) {

eachColorWatch.init();

if (colorToPoints.get(color).size() < 750) {

ArrayList<Stitch> stitches = colorToStitches.get(color);
stitches.add(new Stitch(new Point(-1, -1), new Point(-1, -1)));
this.stitches = stitches;

numStitches = stitches.size();

setDistance(stitches);

initializeIndex(stitches);

improve(eachColorTime, stitches);

sumBackLength += calculateScore();

numStitches--;
int startIndex = -1;
for (int i = 0; i < index2stitch.length; i++) {
if (index2stitch[i] == numStitches) {
startIndex = i;
break;
}
}

if (startIndex == -1) {
throw new AssertionError();
}

ArrayList<Stitch> path = new ArrayList<>();
boolean[] isUpper2 = new boolean[numStitches];
for (int i = startIndex + 1; i < startIndex + index2stitch.length; i++) {
path.add(stitches.get(index2stitch[i % index2stitch.length]));
isUpper2[i - (startIndex + 1)] = startFromUpper[index2stitch[i % index2stitch.length]];
}

makeResult(ret, color, path, isUpper2);

} else {
ArrayList<Point> points = colorToPoints.get(color);

int[] x = new int[points.size() + 1];
int[] y = new int[points.size() + 1];
for (int i = 0; i < points.size(); i++) {
x[i] = points.get(i).c;
y[i] = points.get(i).r;
}
x[points.size()] = -2;
y[points.size()] = -2;

EuclideanTravellingSalesmanProblem tsp = new EuclideanTravellingSalesmanProblem();
int[] order = tsp.getOrder(x, y, eachColorTime);

sumLoops += tsp.loop;
sumTries += tsp.tries;
sumAccepts += tsp.ac;

int startIndex = -1;
for (int i = 0; i < order.length; i++) {
if (order[i] == points.size()) {
startIndex = i;
break;
}
}

if (startIndex == -1) {
throw new AssertionError();
}

ArrayList<Point> pathStitch = new ArrayList<>();
for (int i = startIndex + 1; i < startIndex + order.length; i++) {
pathStitch.add(points.get(order[i % order.length]));
}

ArrayList<Stitch> stitches = greedy(color, pathStitch);
stitches.add(new Stitch(new Point(-2, -2), new Point(-2, -2)));

boolean[] startFromUpper = new boolean[stitches.size()];
for (int i = 0; i < stitches.size(); i++) {
startFromUpper[i] = true;
Stitch stitch = stitches.get(i);
if (stitch.upper.r < stitch.lower.r) {
startFromUpper[i] = !true;

Point swap = stitch.upper;
stitch.upper = stitch.lower;
stitch.lower = swap;
}
}

for (int k = 0; k < 5; k++) {
greedy2opt(stitches, startFromUpper);
}
startIndex = -1;
for (int i = 0; i < stitches.size(); i++) {
if (stitches.get(i).upper.r < 0) {
startIndex = i;
break;
}
}

if (startIndex == -1) {
throw new AssertionError();
}

ArrayList<Stitch> path = new ArrayList<>();
boolean[] isUpper2 = new boolean[stitches.size() - 1];
for (int i = startIndex + 1; i < startIndex + stitches.size(); i++) {
path.add(stitches.get(i % stitches.size()));
isUpper2[i - (startIndex + 1)] = startFromUpper[i % stitches.size()];
}

makeResult(ret, color, path, isUpper2);
}

}

int numPoints = 0;
for (Integer color : colorToPoints.keySet()) {
numPoints += colorToPoints.get(color).size();
}
lengthFront = Math.sqrt(2) * 2 * numPoints;

double score = calculateRawScore(lengthFront, lengthBack);
Utils.debug("score", (int) (1e6 * score), "front", (int) (1e2 * lengthFront), "back", (int) (1e2 * lengthBack), "time", watch.getSecondString());
Utils.debug("score", (int) (1e6 * calculateRawScore(lengthFront, sumBackLength)), "front", (int) (1e2 * lengthFront), "back", (int) (1e2 * sumBackLength), "time", watch.getSecondString());
Utils.debug("sumLoops", sumLoops, "try/loop", String.format("%.1f%%", (double) 100.0 * sumTries / sumLoops), "AC/try", String.format("%.1f%%", (double) 100.0 * sumAccepts / sumTries));

return (String[]) ret.toArray(new String[ret.size()]);
}

private ArrayList<Stitch> greedy(Integer color, ArrayList<Point> path) {

ArrayList<Stitch> ret = new ArrayList<>();
if (path.size() == 1) {

Point point = path.get(0);

int minD = 0;

ret.add(new Stitch(new Point(point.r + dr[minD], point.c + dc[minD]), new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[((minD + 1) % 4) ^ 2], point.c + dc[((minD + 1) % 4) ^ 2]), new Point(point.r + dr[(minD + 1) % 4], point.c + dc[(minD + 1) % 4])));

return ret;
}

Point previousPoint = null;
for (int i = 0; i < path.size() - 1; i++) {
Point point = path.get(i);
Point nextPoint = path.get(i + 1);

if (i == 0) {

double minDistance = 1e9;
int minD = -1;
for (int d = 0; d < dr.length; d++) {
double distance = distance(point.r + dr[d], point.c + dc[d], nextPoint.r + 0.5, nextPoint.c + 0.5);
if (distance < minDistance) {
minDistance = distance;
minD = d;
}
}

if (minD == -1) {
throw new AssertionError();
}

ret.add(new Stitch(new Point(point.r + dr[(minD + 1) % 4], point.c + dc[(minD + 1) % 4]), new Point(point.r + dr[((minD + 1) % 4) ^ 2], point.c + dc[((minD + 1) % 4) ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2]), new Point(point.r + dr[minD], point.c + dc[minD])));

previousPoint = new Point(point.r + dr[minD], point.c + dc[minD]);

} else {

double minDistance = 1e9;
int minD = -1;
int minD2 = -1;
for (int d = 0; d < dr.length; d++) {
if (point.r + dr[d] == previousPoint.r && point.c + dc[d] == previousPoint.c) {
continue;
}
double distanceToPrevious = distance(point.r + dr[d], point.c + dc[d], previousPoint.r, previousPoint.c);

{
int d2 = (d + 1) % 4;
double distance = distance(point.r + dr[d2], point.c + dc[d2], nextPoint.r + 0.5, nextPoint.c + 0.5);
if (distanceToPrevious + distance < minDistance) {
minDistance = distanceToPrevious + distance;
minD = d;
minD2 = d2;
}
}
{
int d2 = (d + 3) % 4;
double distance = distance(point.r + dr[d2], point.c + dc[d2], nextPoint.r + 0.5, nextPoint.c + 0.5);
if (distanceToPrevious + distance < minDistance) {
minDistance = distanceToPrevious + distance;
minD = d;
minD2 = d2;
}
}
}

if (minD == -1) {
throw new AssertionError();
}

ret.add(new Stitch(new Point(point.r + dr[minD], point.c + dc[minD]), new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[minD2 ^ 2], point.c + dc[minD2 ^ 2]), new Point(point.r + dr[minD2], point.c + dc[minD2])));

previousPoint = new Point(point.r + dr[minD2], point.c + dc[minD2]);

}
}
{

Point point = path.get(path.size() - 1);

double minDistance = 1e9;
int minD = -1;
for (int d = 0; d < dr.length; d++) {
if (previousPoint != null && point.r + dr[d] == previousPoint.r && point.c + dc[d] == previousPoint.c) {
continue;
}
double distanceToPrevious = distance(point.r + dr[d], point.c + dc[d], previousPoint.r, previousPoint.c);
if (distanceToPrevious < minDistance) {
minDistance = distanceToPrevious;
minD = d;
}
}

if (minD == -1) {
throw new AssertionError();
}

ret.add(new Stitch(new Point(point.r + dr[minD], point.c + dc[minD]), new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[((minD + 1) % 4) ^ 2], point.c + dc[((minD + 1) % 4) ^ 2]), new Point(point.r + dr[(minD + 1) % 4], point.c + dc[(minD + 1) % 4])));

previousPoint = new Point(point.r + dr[minD], point.c + dc[minD]);

}
return ret;
}

private int greedyLoop = 0;
private int greedyTry = 0;
private int greedyAC = 0;
private int greedyImprove = 0;

private void greedy2opt(ArrayList<Stitch> stitches, boolean[] startFromUpper) {
for (int i = 0; i < stitches.size(); i++) {
for (int i2 = i + 1; i2 <= i + 64; i2++) {
greedyLoop++;
if (i2 < 0 || i2 >= stitches.size()) {
continue;
}

int B = i;
int A = B - 1;
if (A < 0) {
A = stitches.size() - 1;
}

int C = i2;
int D = C + 1;
if (D == stitches.size()) {
D = 0;
}

Point pointA = startFromUpper[A] ? stitches.get(A).lower : stitches.get(A).upper;
Point pointB = startFromUpper[B] ? stitches.get(B).upper : stitches.get(B).lower;
double distanceAB = distance(pointA.r, pointA.c, pointB.r, pointB.c);
if (distanceAB < 1e-9) {
distanceAB = 1e9;
}
if (pointA.r < 0 || pointB.r < 0) {
distanceAB = 0;
}
Point pointC = startFromUpper[C] ? stitches.get(C).lower : stitches.get(C).upper;
Point pointD = startFromUpper[D] ? stitches.get(D).upper : stitches.get(D).lower;
double distanceCD = distance(pointC.r, pointC.c, pointD.r, pointD.c);
if (distanceCD < 1e-9) {
distanceCD = 1e9;
}
if (pointC.r < 0 || pointD.r < 0) {
distanceCD = 0;
}
double AB_CD = distanceAB + distanceCD;
double distanceAC = distance(pointA.r, pointA.c, pointC.r, pointC.c);
if (distanceAC < 1e-9) {
continue;
}
if (pointA.r < 0 || pointC.r < 0) {
distanceAC = 0;
}
double distanceBD = distance(pointB.r, pointB.c, pointD.r, pointD.c);
if (distanceBD < 1e-9) {
continue;
}
if (pointB.r < 0 || pointD.r < 0) {
distanceBD = 0;
}
double AC_BD = distanceAC + distanceBD;

greedyTry++;
if (AC_BD < AB_CD) {
greedyAC++;
greedyImprove += AB_CD - AC_BD;
if (B <= C) {
for (int l = B, r = C; l <= r; l++, r--) {
if (l < r) {
Collections.swap(stitches, l, r);

boolean swap = !startFromUpper[l];
startFromUpper[l] = !startFromUpper[r];
startFromUpper[r] = swap;
} else {
startFromUpper[l] = !startFromUpper[l];
}
}
} else {
for (int l = C + 1, r = B - 1; l <= r; l++, r--) {
if (l < r) {
Collections.swap(stitches, l, r);

boolean swap = !startFromUpper[l];
startFromUpper[l] = !startFromUpper[r];
startFromUpper[r] = swap;
} else {
startFromUpper[l] = !startFromUpper[l];
}
}
}
}

}
}
}

private double calculateRawScore(double front, double back) {
return Math.max(0, Math.pow((5 - back / front) / 5, 3));
}

private void findNearestCities(ArrayList<Stitch> stitches) {
stitch2nearestStitches = new IntArray[numStitches];
for (int i = 0; i < numStitches; i++) {
ArrayList<Pair<Double, Integer>> list = new ArrayList<>();
for (int j = 0; j < numStitches; j++) {
if (j == i) {
continue;
}
list.add(new Pair<Double, Integer>(distancesStitchTo4PointOfStitch[2 * i][2 * j], j));
}
Collections.sort(list);
stitch2nearestStitches[i] = new IntArray();
for (int j = 0; j < Math.min(Math.max(20, 10000 / numStitches), list.size()); j++) {
stitch2nearestStitches[i].add(list.get(j).second);
}
}
}

Watch eachColorWatch = new Watch();

private void improve(double second, ArrayList<Stitch> stitches) {
double score = calculateScore();
double endTemperature = 0, startTemperature = 1e-3, expTemperature = 1.0, temperature = startTemperature;
double startTime = eachColorWatch.getSecond(), endTime = second, time = startTime;
int loop = 0;

int mask = (1 << 8) - 1;

for (;; loop++) {
if ((loop & mask) == mask) {
time = eachColorWatch.getSecond();

if (time >= endTime) {
sumLoops += loop;
break;
}

temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), expTemperature);

}

if (xorShift.nextDouble() < 1.5) {
int B = 1 + (int) ((numStitches - 1) * xorShift.nextDouble());
int A = B - 1;
IntArray nearestStitches = stitch2nearestStitches[index2stitch[A]];
int randomIndex = (int) (nearestStitches.length * xorShift.nextDouble());
int stitch = nearestStitches.values[randomIndex];
int c = stitch2index[stitch];

int C = c;
int D = c + 1;
if (D == numStitches) {
D = 0;
}
double distanceAB = distance(index2stitch[A], index2stitch[B], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[B]] ? 0 : 2));
double distanceCD = distance(index2stitch[C], index2stitch[D], (startFromUpper[index2stitch[C]] ? 1 : 0) + (startFromUpper[index2stitch[D]] ? 0 : 2));
double AB_CD = distanceAB + distanceCD;
double distanceAC = distance(index2stitch[A], index2stitch[C], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[C]] ? 2 : 0));
double distanceBD = distance(index2stitch[B], index2stitch[D], (startFromUpper[index2stitch[B]] ? 0 : 1) + (startFromUpper[index2stitch[D]] ? 0 : 2));
double AC_BD = distanceAC + distanceBD;

sumTries++;
if (AC_BD <= AB_CD || (-AC_BD + AB_CD > -10 * (score * temperature) && (xorShift.nextInt() & 2147483647) < 1 << (int) (31.5 + (-AC_BD + AB_CD) / (score * temperature)))) {
if (!isValidCurrentFlip(A, C)) {
sumTries--;
continue;
}
if (!isValidFlipCurrent(B, D)) {
sumTries--;
continue;
}
sumAccepts++;

score += (AC_BD - AB_CD);
if (B <= C) {
for (int l = B, r = C; l <= r; l++, r--) {
int swap = index2stitch[l];
index2stitch[l] = index2stitch[r];
index2stitch[r] = swap;

stitch2index[index2stitch[l]] = l;
stitch2index[index2stitch[r]] = r;

startFromUpper[index2stitch[l]] = !startFromUpper[index2stitch[l]];
if (l < r) {
startFromUpper[index2stitch[r]] = !startFromUpper[index2stitch[r]];
}
}
} else {
for (int l = C + 1, r = B - 1; l <= r; l++, r--) {
int swap = index2stitch[l];
index2stitch[l] = index2stitch[r];
index2stitch[r] = swap;

stitch2index[index2stitch[l]] = l;
stitch2index[index2stitch[r]] = r;

startFromUpper[index2stitch[l]] = !startFromUpper[index2stitch[l]];
if (l < r) {
startFromUpper[index2stitch[r]] = !startFromUpper[index2stitch[r]];
}
}
}
}
} else {

int A = (int) (numStitches * xorShift.nextDouble());
int B = A + 1;
if (B == numStitches) {
B = 0;
}
int C = B + 1;
if (C == numStitches) {
C = 0;
}

if (!isValidCurrentFlip(A, B)) {
continue;
}
if (!isValidFlipCurrent(B, C)) {
continue;
}
double ABC = distance(index2stitch[A], index2stitch[B], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[B]] ? 0 : 2)) + distance(index2stitch[B], index2stitch[C], (startFromUpper[index2stitch[B]] ? 1 : 0) + (startFromUpper[index2stitch[C]] ? 0 : 2));
double nextABC = distance(index2stitch[A], index2stitch[B], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[B]] ? 2 : 0)) + distance(index2stitch[B], index2stitch[C], (startFromUpper[index2stitch[B]] ? 0 : 1) + (startFromUpper[index2stitch[C]] ? 0 : 2));

if (nextABC <= ABC || (-nextABC + ABC > -10 * (score * temperature) && (xorShift.nextInt() & 2147483647) < 1 << (int) (31.5 + (-nextABC + ABC) / (score * temperature)))) {

score += (nextABC - ABC);

startFromUpper[index2stitch[B]] = !startFromUpper[index2stitch[B]];

}

}
}
}

private boolean isValidCurrentFlip(int A, int C) {
if (startFromUpper[index2stitch[A]]) {
Point pointALower = stitches.get(index2stitch[A]).lower;
if (startFromUpper[index2stitch[C]]) {
Point pointCLooer = stitches.get(index2stitch[C]).lower;
if (pointALower.r == pointCLooer.r && pointALower.c == pointCLooer.c) {
return false;
}
} else {
Point pointCUpper = stitches.get(index2stitch[C]).upper;
if (pointALower.r == pointCUpper.r && pointALower.c == pointCUpper.c) {
return false;
}
}
} else {
Point pointAUpper = stitches.get(index2stitch[A]).upper;
if (startFromUpper[index2stitch[C]]) {
Point pointCLooer = stitches.get(index2stitch[C]).lower;
if (pointAUpper.r == pointCLooer.r && pointAUpper.c == pointCLooer.c) {
return false;
}
} else {
Point pointCUpper = stitches.get(index2stitch[C]).upper;
if (pointAUpper.r == pointCUpper.r && pointAUpper.c == pointCUpper.c) {
return false;
}
}
}
return true;
}

private boolean isValidFlipCurrent(int B, int D) {
if (startFromUpper[index2stitch[B]]) {
Point pointBUpper = stitches.get(index2stitch[B]).upper;
if (startFromUpper[index2stitch[D]]) {
Point pointDUpper = stitches.get(index2stitch[D]).upper;
if (pointBUpper.r == pointDUpper.r && pointBUpper.c == pointDUpper.c) {
return false;
}
} else {
Point pointDLower = stitches.get(index2stitch[D]).lower;
if (pointBUpper.r == pointDLower.r && pointBUpper.c == pointDLower.c) {
return false;
}
}
} else {
Point pointBLower = stitches.get(index2stitch[B]).lower;
if (startFromUpper[index2stitch[D]]) {
Point pointDUpper = stitches.get(index2stitch[D]).upper;
if (pointBLower.r == pointDUpper.r && pointBLower.c == pointDUpper.c) {
return false;
}
} else {
Point pointDLower = stitches.get(index2stitch[D]).lower;
if (pointBLower.r == pointDLower.r && pointBLower.c == pointDLower.c) {
return false;
}
}
}
return true;
}

private double distance(int AFrom, int BTo, int deltaIndex) {
if (stitches.get(AFrom).upper.r < 0 || stitches.get(BTo).upper.r < 0) {
return 0;
}
int r0 = (deltaIndex & 1) == 0 ? stitches.get(AFrom).upper.r : stitches.get(AFrom).lower.r;
int c0 = (deltaIndex & 1) == 0 ? stitches.get(AFrom).upper.c : stitches.get(AFrom).lower.c;
int r1 = (deltaIndex & 2) == 0 ? stitches.get(BTo).upper.r : stitches.get(BTo).lower.r;
int c1 = (deltaIndex & 2) == 0 ? stitches.get(BTo).upper.c : stitches.get(BTo).lower.c;
return distance(r0, c0, r1, c1);
}

private void initializeIndex(ArrayList<Stitch> stitches) {
index2stitch = new int[numStitches];
stitch2index = new int[numStitches];
startFromUpper = new boolean[numStitches];
for (int i = 0; i < index2stitch.length; i++) {
index2stitch[i] = i;
stitch2index[index2stitch[i]] = i;
startFromUpper[i] = true;
if (i == 0) {

} else {
if (startFromUpper[i - 1]) {
if (stitches.get(i).upper.r == stitches.get(i - 1).lower.r && stitches.get(i).upper.c == stitches.get(i - 1).lower.c) {
startFromUpper[i] = !true;
}
} else {
if (stitches.get(i).upper.r == stitches.get(i - 1).upper.r && stitches.get(i).upper.c == stitches.get(i - 1).upper.c) {
startFromUpper[i] = !true;
}
}
}
}

}

private void setDistance(ArrayList<Stitch> stitches) {
int n = 10;
int clusterSize = (S + 1) / n + ((S + 1) % n > 0 ? 1 : 0);
IntArray[][] cluster = new IntArray[clusterSize][clusterSize];
for (int r = 0; r < cluster.length; r++) {
for (int c = 0; c < cluster[r].length; c++) {
cluster[r][c] = new IntArray();
}
}
for (int i = 0; i < numStitches; i++) {
Stitch stitch = stitches.get(i);
int clusterR = stitch.upper.r / n;
int clusterC = stitch.upper.c / n;
cluster[clusterR][clusterC].add(i);
}

PriorityQueue[] distanceStitchToStitch = new PriorityQueue[numStitches];
for (int i = 0; i < distanceStitchToStitch.length; i++) {
distanceStitchToStitch[i] = new PriorityQueue<Pair<Double, Integer>>(new Comparator<Pair<Double, Integer>>() {
@Override
public int compare(Pair<Double, Integer> o1, Pair<Double, Integer> o2) {
if (o1.first.doubleValue() > o2.first.doubleValue()) {
return -1;
}
if (o1.first.doubleValue() < o2.first.doubleValue()) {
return 1;
}
return 0;
}
});
}
for (int i = 0; i < numStitches; i++) {
Stitch stitch = stitches.get(i);

int clusterR = stitch.upper.r / n;
int clusterC = stitch.upper.c / n;

for (int r = clusterR - 1; r <= clusterR + 1; r++) {
if (r < 0 || r >= cluster.length) {
continue;
}
for (int c = clusterC - 1; c <= clusterC + 1; c++) {
if (c < 0 || c >= cluster[r].length) {
continue;
}

for (int k = 0; k < cluster[r][c].length; k++) {

int j = cluster[r][c].values[k];
if (j == i) {
continue;
}
Stitch stitchJ = stitches.get(j);
if (stitch.upper.r < 0 || stitchJ.upper.r < 0) {
distanceStitchToStitch[i].add(new Pair<Double, Integer>(0.0, j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
} else {
double dx = stitchJ.upper.c - stitch.upper.c;
double dy = stitchJ.upper.r - stitch.upper.r;
distanceStitchToStitch[i].add(new Pair<Double, Integer>(Math.sqrt(dx * dx + dy * dy), j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
}

}

{

int j = numStitches - 1;
if (j == i) {
continue;
}
Stitch stitchJ = stitches.get(j);
if (stitch.upper.r < 0 || stitchJ.upper.r < 0) {
distanceStitchToStitch[i].add(new Pair<Double, Integer>(0.0, j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
} else {
double dx = stitchJ.upper.c - stitch.upper.c;
double dy = stitchJ.upper.r - stitch.upper.r;
distanceStitchToStitch[i].add(new Pair<Double, Integer>(Math.sqrt(dx * dx + dy * dy), j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
}

}

}
}
}

distancesStitchTo4PointOfStitch = new double[numStitches][4 * 32];
stitch2nearestStitches = new IntArray[numStitches];
stitch2nearestStitchIndex2index = new HashMap<Integer, HashMap<Integer, Integer>>();

for (int i = 0; i < numStitches; i++) {
stitch2nearestStitches[i] = new IntArray(32);
for (int j = 0; !distanceStitchToStitch[i].isEmpty(); j++) {
Pair<Double, Integer> distanceAndStitchIndexPair = (Pair<Double, Integer>) distanceStitchToStitch[i].poll();
int k = 4 * j;

Stitch stitchFrom = stitches.get(i);
Stitch stitchTo = stitches.get(distanceAndStitchIndexPair.second.intValue());
if (stitchFrom.upper.r < 0 || stitchTo.upper.r < 0) {
distancesStitchTo4PointOfStitch[i][k + 0] = 0;
distancesStitchTo4PointOfStitch[i][k + 1] = 0;
distancesStitchTo4PointOfStitch[i][k + 2] = 0;
distancesStitchTo4PointOfStitch[i][k + 3] = 0;
} else {
distancesStitchTo4PointOfStitch[i][k + 0] = distance(stitchFrom.upper.r, stitchFrom.upper.c, stitchTo.upper.r, stitchTo.upper.c);
distancesStitchTo4PointOfStitch[i][k + 1] = distance(stitchFrom.upper.r, stitchFrom.upper.c, stitchTo.lower.r, stitchTo.lower.c);
distancesStitchTo4PointOfStitch[i][k + 2] = distance(stitchFrom.lower.r, stitchFrom.lower.c, stitchTo.upper.r, stitchTo.upper.c);
distancesStitchTo4PointOfStitch[i][k + 3] = distance(stitchFrom.lower.r, stitchFrom.lower.c, stitchTo.lower.r, stitchTo.lower.c);
}
stitch2nearestStitches[i].add(distanceAndStitchIndexPair.second.intValue());

if (stitch2nearestStitchIndex2index.get(i) == null) {
stitch2nearestStitchIndex2index.put(i, new HashMap<Integer, Integer>());
}
stitch2nearestStitchIndex2index.get(i).put(distanceAndStitchIndexPair.second, k);
}
}
}

private double[] currentDistance;

private double calculateScore() {
double score = 0.0;
currentDistance = new double[numStitches];
for (int i = 0; i < numStitches; i++) {
int j = i + 1;
if (j == numStitches) {
j = 0;
}
int from = index2stitch[i];
int to = index2stitch[j];
double distance = distance(from, to, (startFromUpper[from] ? 1 : 0) + (startFromUpper[to] ? 0 : 2));
score += distance;
currentDistance[from] = distance;
}
return score;
}

private static final int[] dr = new int[] { 0, 0, 1, 1, };
private static final int[] dc = new int[] { 0, 1, 1, 0, };

private void makeResult(ArrayList<String> ret, Integer color, ArrayList<Stitch> path, boolean[] isUpper) {
ret.add("" + (char) (color + 'a'));

for (int i = 0; i < path.size(); i++) {

Stitch stitch = path.get(i);

if (isUpper[i]) {
ret.add(stitch.upper.r + " " + stitch.upper.c);
if (i == 0) {
lengthBack += 0;
} else {
Stitch previousStitch = path.get(i - 1);
if (isUpper[i - 1]) {
lengthBack += distance(stitch.upper.r, stitch.upper.c, previousStitch.lower.r, previousStitch.lower.c);
} else {
lengthBack += distance(stitch.upper.r, stitch.upper.c, previousStitch.upper.r, previousStitch.upper.c);
}
}
ret.add(stitch.lower.r + " " + stitch.lower.c);
lengthFront += Math.sqrt(2);
} else {
ret.add(stitch.lower.r + " " + stitch.lower.c);
if (i == 0) {
lengthBack += 0;
} else {
Stitch previousStitch = path.get(i - 1);
if (isUpper[i - 1]) {
lengthBack += distance(stitch.lower.r, stitch.lower.c, previousStitch.lower.r, previousStitch.lower.c);
} else {
lengthBack += distance(stitch.lower.r, stitch.lower.c, previousStitch.upper.r, previousStitch.upper.c);
}
}
ret.add(stitch.upper.r + " " + stitch.upper.c);
lengthFront += Math.sqrt(2);
}

}
}

private void init(String[] pattern) {
S = pattern.length;

for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {

char charAt = pattern[r].charAt(c);
if (charAt == '.') {
continue;
}

int color = charAt - 'a';

if (colorToPoints.get(color) == null) {
colorToPoints.put(color, new ArrayList<Point>());
}
colorToPoints.get(color).add(new Point(r, c));

if (colorToStitches.get(color) == null) {
colorToStitches.put(color, new ArrayList<Stitch>());
}
colorToStitches.get(color).add(new Stitch(new Point(r, c), new Point(r + 1, c + 1)));
colorToStitches.get(color).add(new Stitch(new Point(r + 1, c), new Point(r, c + 1)));
}
}

{
int numColors = colorToPoints.keySet().size();
int numPoints = 0;
for (Integer color : colorToPoints.keySet()) {
numPoints += colorToPoints.get(color).size();
}
Utils.debug("S", S, "numColors", numColors, "numPoints", numPoints);
}
}

private double distance(double r0, double c0, double r1, double c1) {
double dr = r1 - r0;
double dc = c1 - c0;
return Math.sqrt(dr * dr + dc * dc);
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

int S = Integer.parseInt(br.readLine());
String[] pattern = new String[S];
for (int i = 0; i < S; ++i) {
pattern[i] = br.readLine();
}

CrossStitch cs = new CrossStitch();
String[] ret = cs.embroider(pattern);

System.out.println(ret.length);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}

class Point {
int r;
int c;

public Point(int r, int c) {
super();
this.r = r;
this.c = c;
}
}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}

class Watch {
private long start;

public Watch() {
init();
}

public double getSecond() {
return (System.nanoTime() - start) * 1e-9;
}

public void init() {
init(System.nanoTime());
}

private void init(long start) {
this.start = start;
}

public String getSecondString() {
return toString(getSecond());
}

public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}

}

class EuclideanTravellingSalesmanProblem {
private int N;
private int[] x;
private int[] y;
private XorShift xorShift = new XorShift(System.nanoTime());
private double[][] distance;
private int[] index2city;
private int[] city2index;
private IntArray[] city2nearestCities;

private Watch watch = new Watch();

public int[] getOrder(int[] x, int[] y, double second) {
watch.init();

this.N = x.length;
this.x = x;
this.y = y;
setDistance();
findNearestCities();
initializeIndex();
improve(second);
return index2city;
}

private void findNearestCities() {
city2nearestCities = new IntArray[N];
for (int i = 0; i < N; i++) {
ArrayList<Pair<Double, Integer>> list = new ArrayList<>();
for (int j = 0; j < N; j++) {
if (j == i) {
continue;
}
list.add(new Pair<Double, Integer>(distance[i][j], j));
}
Collections.sort(list);
city2nearestCities[i] = new IntArray();
for (int j = 0; j < Math.min(Math.max(20, 10000 / N), list.size()); j++) {
city2nearestCities[i].add(list.get(j).second);
}
}
}

int loop = 0;
int tries = 0;
int ac = 0;

private void improve(double second) {
double score = getScore();
double endTemperature = 0, startTemperature = 1e-3, expTemperature = 1.5, temperature = startTemperature;
double startTime = watch.getSecond(), endTime = second, time = startTime;

int mask = (1 << 8) - 1;

for (;; loop++) {
if ((loop & mask) == mask) {
time = watch.getSecond();

if (time >= endTime) {
break;
}

temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), expTemperature);

}

int B = 1 + (int) ((N - 1) * xorShift.nextDouble());
int A = B - 1;
IntArray s = city2nearestCities[index2city[A]];
int c = city2index[s.values[(int) (s.length * xorShift.nextDouble())]];

int C = c;
int D = c + 1;
if (D == N) {
D = 0;
}
double ABCDEF = distance[index2city[A]][index2city[B]] + distance[index2city[C]][index2city[D]];
double ACBDEF = distance[index2city[A]][index2city[C]] + distance[index2city[B]][index2city[D]];
tries++;
if (ACBDEF <= ABCDEF || (-ACBDEF + ABCDEF > -10 * (score * temperature) && (xorShift.nextInt() & 2147483647) < 1 << (int) (31.5 + (-ACBDEF + ABCDEF) / (score * temperature)))) {
ac++;
score = score + (ACBDEF - ABCDEF);

if (B <= C) {
for (int l = B, r = C; l < r; l++, r--) {
int swap = index2city[l];
index2city[l] = index2city[r];
index2city[r] = swap;
city2index[index2city[l]] = l;
city2index[index2city[r]] = r;
}
} else {
for (int l = C + 1, r = B - 1; l < r; l++, r--) {
int swap = index2city[r];
index2city[r] = index2city[l];
index2city[l] = swap;
city2index[index2city[r]] = r;
city2index[index2city[l]] = l;
}
}
}
}
}

private void initializeIndex() {
index2city = new int[N];
city2index = new int[N];
for (int i = 0; i < index2city.length; i++) {
index2city[i] = i;
city2index[index2city[i]] = i;
}

}

private void setDistance() {
distance = new double[N][N];
for (int i = 0; i < distance.length; i++) {
for (int j = 0; j < i; j++) {
if (x[i] < 0 || x[j] < 0) {
distance[i][j] = 0;
} else {
double dx = x[i] - x[j];
double dy = y[i] - y[j];
distance[i][j] = Math.sqrt(dx * dx + dy * dy);
}
distance[j][i] = distance[i][j];
}
}
}

private double getScore() {
double score = 0.0;
for (int i = 0; i < N; i++) {
int j = i + 1;
if (j == N) {
j = 0;
}
int from = index2city[i];
int to = index2city[j];
score += distance[from][to];
}
return score;
}

}

class IntArray {
public int[] values;
public int length;

public IntArray() {
this(new int[4], 0);
}

public IntArray(int capacity) {
this(new int[capacity], 0);
}

public IntArray(int[] values) {
this(values, values.length);
}

public IntArray(int[] values, int length) {
this.values = values;
this.length = length;
}

public void add(int value) {
if (length == values.length) {
values = Arrays.copyOf(values, values.length << 1);
}
values[length++] = value;
}

public int remove() {
return values[--length];
}

public boolean contains(int value) {
for (int i = 0; i < length; i++) {
if (values[i] == value) {
return true;
}
}
return false;
}

public void clear() {
length = 0;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < length; i++) {
sb.append(values[i] + ",");
}
sb.append("}");
return sb.toString();
}

public boolean isEmpty() {
return length == 0;
}

public int remove(int index) {
if (index >= length) {
throw new AssertionError();
}

if (index == length - 1) {
return remove();
}

int res = values[index];
System.arraycopy(values, index + 1, values, index, length - (index + 1));
length--;

return res;
}

public void set(int index, int value) {
if (index >= length) {
throw new AssertionError();
}

if (length >= values.length - 1) {
values = Arrays.copyOf(values, values.length << 1);
}
System.arraycopy(values, index, values, index + 1, length - index);
length++;

values[index] = value;
}

public IntArray copy() {
return new IntArray(Arrays.copyOf(values, length), length);
}

public int[] toArray() {
return Arrays.copyOf(values, length);
}

}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift(long l) {
x = (int) l;
}

public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

public long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

public int nextInt(int n) {
return (int) (n * nextDouble());
}

}

class Stitch {
Point upper;
Point lower;

public Stitch(Point a, Point b) {
super();
this.upper = a;
this.lower = b;
}

}