Разбор задачи, которая поможет размять извилины и заодно даст понимание того, как вы умеете применять алгоритмы на практике.
8К открытий8К показов
Сергей Мясников
старший разработчик приложения «Яндекс»,
автор задач в <a href="https://yandex.ru/cup/mobile">Yandex Cup</a>
Если осенняя хандра застала вас еще в начале осени, то пришла пора немного взбодриться. Яндекс поделился любопытной задачей, которая не только поможет отвлечься от непогоды, но еще и проверит, насколько вы разбираетесь в мобильной разработке. Кстати, подобные задачи будут на чемпионате по программированию Yandex Cup в этом году.
Задача
Машины с автоматическим управлением — это круто. Так думаете не только вы, но и все сотрудники компании, в которую вам повезло устроиться. В этой компании как раз пишут софт для управления такими машинами. Для проверки и демонстрации последних достижений в офисе компании есть отдельная комната, моделирующая перекресток дорог шириной W метров и длиной H метров.
Каждая машина имеет ширину 1 и длину, не превышающую размеры перекрестка.
Одна из ситуаций, в которую частенько попадают как обычные водители, так и ИИ, банальна, но оттого не менее неприятна — пробка. Каждый водитель пытается выбраться из нее как можно быстрее, порой совершая маневры, ухудшающие ситуацию для всех окружающих. Но если бы все машины управлялись автоматикой, насколько быстрее разрешалась бы проблема? Именно на этот вопрос и должна ответить демонстрация, для которой вы должны написать код.
В начале демонстрации на перекрёсток будет помещено N машин. Для упрощения расчетов каждая машина ориентирована либо горизонтально, либо вертикально. Каждую секунду каждая из машин может переместиться на 1, если ей ничего не мешает. Пробка считается разрешенной, если на перекрестке не осталось ни одной машины. Реализуйте алгоритм, позволяющий сделать это за наименьшее количество времени.
Ограничение по времени: 10 секунд.
Ограничение по памяти: 512Mb.
Ввод: стандартный ввод или input.txt.
Вывод: стандартный вывод или output.txt.
Формат ввода
Первая строка содержит 2 числа — 0 < W < 13, 0 < H < 13. Гарантируется, что W * H ≤ 25. Вторая строка содержит число 0 ≤ N< 13. Следующие N строк содержат по 4 числа каждая — x1i, y1i, x2i, y2i, 0 < x1, x2 ≤ W, 0 < y1, y2 ≤ H — координаты левого верхнего и нижнего правого углов машины i. Гарантируется, что либо x1i = x2i, либо y1i = y2i.
Формат вывода
На первой строке выведите количество секунд, необходимых для очищения перекрёстка. В последующих строках выведите информацию о перемещениях машин посекундно. Каждая секунда описывается так:
Количество машин, переместившихся в эту секунду.
Для каждой из двигавшихся машин — номер машины(нумерация с 1) и направление, в котором она перемещалась, ‘L’ влево, ‘R’ вправо, ‘U’ вверх и ‘D’ вниз.
Обратите внимание — все движения в течение одной секунды происходят одновременно.
Задача соревновательная, и вам необязательно написать «правильное» решение, всегда находящее идеальную стратегию. Чем ближе ваш ответ к оптимальному, тем больше баллов вы получите.
Каждый тест оценивается в зависимости от размера входных данных.
За совершение невозможных движений (таких, в результате которых машины будут «наезжать» друг на друга) вы будете получать 0 баллов. Так же оценивается превышение лимита по памяти или времени исполнения и «падения» программы.
Любое корректное решение получает половину или более баллов теста. Чем ближе решение к оптимальному, тем больше будет начислено баллов.
Итоговой оценкой станет сумма баллов, полученных во всех тестах.
Возможное решение
import java.io.PrintWriter;
import java.util.*;
public class CarsSolutionFast {
private static final byte NONE = 0;
private static final byte UP = 1;
private static final byte DOWN = 2;
private static final byte LEFT = 3;
private static final byte RIGHT = 4;
private static final char EMPTY = '.';
private static final char TEMP = '*';
private static final char OCCUPIED = '#';
// 2 ^ 25
private static final int MAX_NODES = 33554432;
private static int w;
private static int h;
private static int n;
private static char[][] map;
// we'll never reach all possible nodes
private static int[] queue = new int[MAX_NODES / 2];
private static int queueStart = 0;
private static int queueEnd = 0;
private static long[] edges = new long[MAX_NODES];
private static int[] parent = new int[MAX_NODES];
private static int current;
private static byte[] moves;
private static byte[] movesToCurrent;
private static int[][] sliding;
private static int[] x1Original;
private static int[] x1;
private static int[] y1Original;
private static int[] y1;
private static int[] x2;
private static int[] x2Original;
private static int[] y2;
private static int[] y2Original;
private static boolean[] isHorizontal;
// initial
// Took 55322ms, allocated 702921216b
// free reverse, no move types
// Took 51782ms, allocated 834216048b
// no moves, history as byte arrays
// Took 43565ms, allocated 392096864b
// static map
// Took 41171ms, allocated 421444792b
// to map as class
// Took 40365ms, allocated 375732824b
// no car class, slide and static moves
// Took 42691ms, allocated 372729376b
// static parent, no visited
// Took 35253ms, allocated 298465792b
// static queue as array
// Took 29393ms, allocated 410415104b
// encoded moves, no hashmaps
// Took 27274ms, allocated 476732320b
// restrict backwards moves
// Took 11344ms, allocated 476732200b
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
w = sc.nextInt();
h = sc.nextInt();
map = new char[w][h];
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
map[i][j] = EMPTY;
}
}
n = sc.nextInt();
if (w * h == 1 || n == 0) {
pw.println(0);
pw.flush();
pw.close();
return;
}
moves = new byte[n];
movesToCurrent = new byte[n];
long startTime = System.currentTimeMillis();
x1 = new int[n];
y1 = new int[n];
x2 = new int[n];
y2 = new int[n];
x1Original = new int[n];
y1Original = new int[n];
x2Original = new int[n];
y2Original = new int[n];
isHorizontal = new boolean[n];
sliding = new int[n][2];
for (int i = 0; i < n; i++) {
byte x1read = (byte) (sc.nextByte() - 1);
byte y1read = (byte) (sc.nextByte() - 1);
byte x2read = (byte) (sc.nextByte() - 1);
byte y2read = (byte) (sc.nextByte() - 1);
x1[i] = x1read;
y1[i] = y1read;
x2[i] = x2read;
y2[i] = y2read;
x1Original[i] = x1read;
y1Original[i] = y1read;
x2Original[i] = x2read;
y2Original[i] = y2read;
isHorizontal[i] = y1[i] == y2[i];
placeCars();
}
int start = encodeMap();
parent[start] = -1;
queue[queueEnd++] = start;
while (queueEnd != queueStart) {
current = queue[queueStart++];
if (current == 0) {
// Yay, found it!
break;
}
decodeMap(current);
tryMoving((byte) 0);
}
List<byte[]> history = new ArrayList<>();
int pointer = 0;
while (parent[pointer] > 0) {
long encodedMoves = edges[pointer];
decodeMoves(encodedMoves, false);
byte[] step = new byte[n];
System.arraycopy(moves, 0, step, 0, n);
history.add(step);
pointer = parent[pointer];
}
Collections.reverse(history);
pw.println(history.size());
for (byte[] moves : history) {
int movesCount = 0;
for (byte move : moves) {
if (move != NONE) {
movesCount++;
}
}
pw.println(movesCount);
for (int i = 0; i < n; i++) {
if (moves[i] != NONE) {
char direction = '.';
switch (moves[i]) {
case UP:
direction = 'U';
break;
case DOWN:
direction = 'D';
break;
case LEFT:
direction = 'L';
break;
case RIGHT:
direction = 'R';
break;
}
pw.println((i + 1) + " " + direction);
}
}
}
// pw.println("Took " + (System.currentTimeMillis() - startTime) + "ms, allocated " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) + "b");
pw.flush();
pw.close();
}
private static long encodeMoves() {
long mult = 1;
long res = 0;
for (int i = 0; i < n; i++) {
res += mult * moves[i];
mult *= 5;
}
return res;
}
private static void decodeMoves(long encoded, boolean first) {
long mult = 1;
for (int i = 0; i < n - 1; i++) {
mult *= 5;
}
for (int i = n - 1; i >= 0; i--) {
moves[i] = (byte) (encoded / mult);
if (first) {
movesToCurrent[i] = moves[i];
}
encoded %= mult;
mult /= 5;
}
}
private static void traceMovesForSlide(int state) {
for (int i = 0; i < n; i++) {
sliding[i][0] = 0;
sliding[i][1] = 0;
}
int pointer = state;
boolean first = true;
while (parent[pointer] > 0) {
decodeMoves(edges[pointer], first);
first = false;
for (int i = 0; i < n; i++) {
switch (moves[i]) {
case UP:
sliding[i][1]--;
break;
case DOWN:
sliding[i][1]++;
break;
case LEFT:
sliding[i][0]--;
break;
case RIGHT:
sliding[i][0]++;
break;
}
}
pointer = parent[pointer];
}
}
private static void tryMoving(byte index) {
if (index == n) {
int encoded = encodeMap();
if (parent[encoded] == 0) {
edges[encoded] = encodeMoves();
parent[encoded] = current;
queue[queueEnd++] = encoded;
}
return;
}
// stay
tryMoving((byte) (index + 1));
byte direction;
if (isHorizontal[index]) {
direction = LEFT;
} else {
direction = UP;
}
if (move(index, direction)) {
moves[index] = direction;
tryMoving((byte) (index + 1));
moves[index] = NONE;
reverse(index, direction == UP ? DOWN : RIGHT);
}
direction = direction == UP ? DOWN : RIGHT;
if (move(index, direction)) {
moves[index] = direction;
tryMoving((byte) (index + 1));
moves[index] = NONE;
reverse(index, direction == DOWN ? UP : LEFT);
}
}
private static int encodeMap() {
int res = 0;
int mult = 1;
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
res += ((map[i][j] == EMPTY || map[i][j] == TEMP) ? 0 : 1) * mult;
mult *= 2;
}
}
return res;
}
private static void decodeMap(int current) {
traceMovesForSlide(current);
resetToOriginal();
for (int i = 0; i < w; i++) {
for (int j = 0; j < h; j++) {
map[i][j] = EMPTY;
}
}
for (int i = 0; i < n; i++) {
x1[i] += sliding[i][0];
x2[i] += sliding[i][0];
y1[i] += sliding[i][1];
y2[i] += sliding[i][1];
}
placeCars();
}
private static void clear(int x, int y) {
set(x, y, EMPTY);
}
private static void setTemp(int x, int y) {
set(x, y, TEMP);
}
private static void occupy(int x, int y) {
set(x, y, OCCUPIED);
}
private static void set(int x, int y, char c) {
if (x < 0) {
return;
}
if (x >= w) {
return;
}
if (y < 0) {
return;
}
if (y >= h) {
return;
}
map[x][y] = c;
}
private static void placeCars() {
for (int i = 0; i < n; i++) {
int start;
int finish;
if (isHorizontal[i]) {
start = Math.max(x1[i], 0);
finish = x2[i] >= w ? w - 1 : x2[i];
for (int j = start; j <= finish; j++) {
map[j][y1[i]] = OCCUPIED;
}
} else {
start = Math.max(y1[i], 0);
finish = y2[i] >= h ? h - 1 : y2[i];
for (int j = start; j <= finish; j++) {
map[x1[i]][j] = OCCUPIED;
}
}
}
}
private static void resetToOriginal() {
for (int i = 0; i < n; i++) {
x1[i] = x1Original[i];
x2[i] = x2Original[i];
y1[i] = y1Original[i];
y2[i] = y2Original[i];
moves[i] = 0;
}
}
private static void reverse(int i, byte direction) {
switch (direction) {
case UP:
clear(x1[i], y2[i]);
y1[i]--;
y2[i]--;
occupy(x1[i], y1[i]);
break;
case DOWN:
clear(x1[i], y1[i]);
y1[i]++;
y2[i]++;
occupy(x1[i], y2[i]);
break;
case LEFT:
clear(x2[i], y2[i]);
x1[i]--;
x2[i]--;
occupy(x1[i], y2[i]);
break;
case RIGHT:
clear(x1[i], y2[i]);
x1[i]++;
x2[i]++;
occupy(x2[i], y2[i]);
break;
}
}
private static boolean move(int i, byte direction) {
switch (direction) {
case UP:
if (movesToCurrent[i] != DOWN && y2[i] <= h - 1 && y2[i] >= 0 && (y1[i] <= 0 || map[x1[i]][y1[i] - 1] == EMPTY)) {
setTemp(x1[i], y2[i]);
y1[i]--;
y2[i]--;
occupy(x1[i], y1[i]);
return true;
}
return false;
case DOWN:
if (movesToCurrent[i] != UP && y1[i] >= 0 && y1[i] <= h - 1 && (y2[i] >= h - 1 || map[x1[i]][y2[i] + 1] == EMPTY)) {
setTemp(x1[i], y1[i]);
y1[i]++;
y2[i]++;
occupy(x1[i], y2[i]);
return true;
}
return false;
case LEFT:
if (movesToCurrent[i] != RIGHT && x2[i] <= w - 1 && x2[i] >= 0 && (x1[i] <= 0 || map[x1[i] - 1][y1[i]] == EMPTY)) {
setTemp(x2[i], y2[i]);
x1[i]--;
x2[i]--;
occupy(x1[i], y2[i]);
return true;
}
return false;
case RIGHT:
if (movesToCurrent[i] != LEFT && x1[i] >= 0 && x1[i] <= w - 1 && (x2[i] >= w - 1 || map[x2[i] + 1][y1[i]] == EMPTY)) {
setTemp(x1[i], y2[i]);
x1[i]++;
x2[i]++;
occupy(x2[i], y2[i]);
return true;
}
return false;
}
return false;
}
}
Объяснение
Рассмотрим случайное расположение машин на поле.
Как несложно заметить при рассмотрении доступных движений, номером машины, занимающей клетку, можно пренебречь. Сопоставим клетке, занятой какой-либо из машин, 1, а свободной — 0.
Такую матрицу можно поставить в соответствие с числом от 0 до 2^(W * H), что, по условию задачи, не более 2^25. Таким образом мы имеем граф, состоящий из вершин, которые представляют собой состояние перекрестка в двоичном виде в определенный момент времени.
Теперь переформулируем задачу — из вершины, заданной начальным расположением машин, необходимо за минимальное количество шагов добраться до нулевой (соответствующей пустому перекрестку).
Для решения этой задачи применим поиск в ширину с последующим восстановлением путей. Ребрами графа, по которому мы делаем поиск в ширину, в данном случае является набор движений всех автомобилей на перекрестке за 1 секунду. Каждый такой набор движений можно закодировать вектором длины N, где каждая компонента описывает движение соответствующей машины (вперед, назад, вверх, вниз или оставить на месте).
Алгоритм можно описать так:
Закодировать начальное положение в номер вершины.
Поместить эту вершину в очередь, пометить расстояние до нее 0.
Пока очередь не пуста:Извлечь вершину из очереди, для нее извлечь и раскодировать набор движений, приведший в нее из начального положения, тем самым восстановив текущее положение машин;Рекурсивно перебрать возможные ребра для текущего положения машин на перекрестке. Для каждого ребра закодировать вершину, в которую оно ведет. Для полученного номера вершины проверить, не подсчитано ли для нее расстояние. Если нет, добавить эту вершину в очередь, изменить расстояние, запомнить текущее ребро как часть пути до этой вершиныВосстановить и вывести путь до вершины 0.
Проблемы, однако, кроются в ограничениях по памяти — для решения на полный балл придется применить побитовое кодирование большинства хранимых данных, отказаться от объектов, а также применить следующие оптимизации:
Не пытаться двигать машину в противоположных направлениях – это никогда не приводит к оптимальному решению.
Для хранения информации о ребре в матрице состояний достаточно числа от 0 до 5 ^ 13. Это позволяет хранить эту информацию одним 32-битным числом, значительно экономя память.
