Минимальное количество кликов для решения головоломки Flood-It-like

У меня есть сетка N × M, в которой каждая ячейка окрашена одним цветом.

Когда игрок нажимает на любую ячейку сетки цвета α, ячейка в верхнем левом углу сетки цвета β, получает цвет α, но не только: все те ячейки, которые подключены к источник по путям, которые используют только цвета α или β, также получают цвет α.

Связь между ячейками следует рассматривать только в горизонтальном и вертикальном направлениях, чтобы сформировать пути. Например, когда игрок нажимает на ячейку, выделенную на рисунке слева, сетка получает раскраску фигуры справа. Цель игры - сделать сетку монохроматической.

Описание ввода

Первая строка ввода состоит из 2 целых чисел N и M (1 ≤ N ≤ 4, 1 ≤ M ≤ 5), которые представляют соответственно количество строк и количество столбцов сетки. После этого N строк описывают начальную конфигурацию сетки, представляя каждый цвет целым числом от 0 до 9. Вход не состоит из любой другой строки.

Описание вывода

Распечатайте строку, содержащую единственное целое число, которое представляет минимальное количество кликов, которые игрок должен сделать, чтобы сделать сетку монохроматической.

Пример ввода

1

4 5
  01234
  34567
  67890
  90123

2:

4 5
  01234
  12345
  23456
  34567

3:

4 5
  00162
  30295
  45033
  01837

Пример вывода

1

12

2:

7

3:

10

Я пытаюсь найти решение с обратным отсчетом (из-за ограничения времени в 8 секунд и небольшого размера сетки). Но это превысило лимит времени. Некоторые люди просто сделали это на 0 секунд.

Есть ли другой алгоритм для решения этой проблемы?

#include <stdio.h>
#include <string.h>

#define MAX 5
#define INF 999999999

typedef int signed_integer;

signed_integer n,m,mink;
bool vst[MAX][MAX];

signed_integer flood_path[4][2] = {
    {-1,0},
    {1,0},
    {0,1},
    {0,-1}
};

//flood and paint all possible cells... the root is (i,j)
signed_integer flood_and_paint(signed_integer cur_grid[MAX][MAX],signed_integer i, signed_integer j, signed_integer beta, signed_integer alpha, signed_integer colors[]){
    //invalid cell
    if (vst[i][j] || i < 0 || i >= n || j < 0 || j >= m)
        return 0;

    //mark existent colors
    colors[cur_grid[i][j]] = 1;

    //only alpha and beta colors counts
    if (cur_grid[i][j] != beta && cur_grid[i][j] != alpha)
        return 0;

    //mark (i,j) as visited and change its color
    vst[i][j] = true;
    cur_grid[i][j] = alpha;

    //floodit !
    signed_integer ret = 1;
    for (signed_integer k = 0; k < 4; k++)
        ret += flood_and_paint(cur_grid,i + flood_path[k][0], j + flood_path[k][1], beta, alpha, colors);

    //how many cells change
    return ret;
}

void backtrack(signed_integer cur_grid[MAX][MAX],signed_integer k,signed_integer _cont, signed_integer alpha) {
    //bigger number of clicks for this solution ? ... getting back
    if(k >= mink)
        return;

    signed_integer colors[10];
    memset(vst, false, sizeof(vst));
    memset(colors, 0, sizeof(colors));

    signed_integer beta = cur_grid[0][0];
    signed_integer cont = flood_and_paint(cur_grid, 0, 0, beta, alpha, colors);

    //there are alpha colors to change and no beta colors to change
    colors[alpha] = 1;
    colors[beta]  = 0;

    //all squares on same color
    if (cont == n * m) {
        mink = k;
        return;
    }

    //this solution is equals to another ? ... getting back
    if (cont == _cont)
        return;

    ++k;//new click

    //copy this matrix and backtrack
    signed_integer copy[MAX][MAX];
    for (signed_integer c = 0; c < 10; ++c){
        if (colors[c] && c != cur_grid[0][0]) {
            memcpy(copy, cur_grid,n*m*sizeof(signed_integer));
            backtrack(copy,k,cont,c);
        }
    }
}

void cleanBuffer(){
     while (getchar() != '\n');
}

int main(void) {
    signed_integer grid[MAX][MAX];
    scanf("%d %d",&n,&m);
    for (signed_integer i = 0; i < n; ++i) {
        cleanBuffer();
        for (signed_integer j = 0; j < m; ++j){
            grid[i][j] = getchar() - '0';
        }
    }
    mink = INF;
    backtrack(grid,0, 0, grid[0][0]);
    printf("%d\n",mink);
    return 0;
}

Ответы

Ответ 1

Улучшение высокого уровня

Обратите внимание, что ячейки являются либо их исходным цветом, либо последним выбранным цветом.

Это означает, что мы можем представить текущее состояние платы с помощью 20 бит (маркировка для каждой из ячеек 4 * 5, если они содержат исходный цвет), и число в диапазоне от 0 до 9, дающее последний выбранный цвет.

Это приведет к исследованию не более 10 миллионов штатов. Функция backtracking может избежать необходимости повторять, если она достигает состояния, которое уже было посещено. Я ожидаю, что это изменение сделает ваше решение значительно быстрее.

Улучшение низкого уровня

Представление состояния с помощью 20-битной маски, а последний цвет также значительно ускоряет обновление и восстановление состояния, так как вместо memcpy всей доски необходимо изменить только 2 номера.

Ответ 2

Если вы думаете о плате 4x5 как "19 квадратов, на которые вы можете щелкнуть", это говорит о том, что есть 19! или 121 645 100 408 832 000 комбинаций для проверки. Тем не менее, существует ряд оптимизаций, которые могут значительно сократить количество комбинаций до нескольких десятков:

наблюдения о стратегии игры

• Нажатие на разные квадраты с одинаковым цветом имеет тот же эффект. Поэтому доску следует рассматривать как "9 цветов (или меньше), на которые вы можете щелкнуть".
• Смежные квадраты с одинаковым цветом следует рассматривать как группы; они всегда действуют сообща. В приведенном ниже примере три белых квадрата внизу справа образуют такую ​​группу.
• Имеет смысл только щелкнуть по цвету, который находится рядом с угловой группой. На первом шаге ниже показан только щелчок на розовом, зеленом, оранжевом или белом квадрате.
• Когда несколько групп с уникальным цветом (где только одна группа имеет определенный цвет) смежны с угловой группой, порядок, в котором они нажаты, не имеет значения. В приведенном ниже примере, после нажатия 5 и 3, любой порядок нажатия 4, 7, 8 и 9 будет иметь тот же результат.
• Когда все группы определенного цвета смежны с угловой группой, их можно рассматривать как группы с уникальным цветом; для их подключения требуется ровно один клик на цвет. В приведенном ниже примере, после нажатия 5 и 3, два розовых квадрата и два зеленых квадрата превращаются в две группы с уникальным цветом.
• Если на доске есть только группы с уникальным цветом, количество необходимых кликов равно числу несвязанных групп. В приведенном ниже примере, после нажатия 5 и 3, требуется ровно восемь кликов.
• Если существует только одна несвязанная группа, которая имеет тот же цвет, что и угловая группа, и они разделены более чем одной другой группой, группу можно рассматривать как группу с уникальным цветом.
• Уменьшение количества кликов означает одновременное подключение нескольких групп. Это можно сделать, когда несколько групп с одинаковым цветом расположены рядом с угловой группой (например, при нажатии 1 или 2 на шаге 3 примера ниже) или нажатием группы, которая отделяет группу углов от группы с тем же цветом ( как это происходит в шагах 1 и 2 в примере).

Алгоритм, основанный на оптимальной стратегии

Рекурсивный алгоритм, основанный на оптимальной стратегии с использованием перечисленных выше правил, проходит через эти шаги для каждой рекурсии:

• Если оставлены только группы с уникальным цветом, количество кликов равно числу несвязанных групп; верните это число.
• Если группа с тем же цветом, что и угловая группа, отделена от нее только одной другой группой, щелкните эту другую группу и запишите ее. Если существует несколько вариантов, попробуйте все из них.
• Если одна или несколько групп уникального цвета (или все группы определенных цветов) смежны с угловой группой, щелкните их все в любом порядке. Затем повторите оценку платы с шага 1.
• Попробуйте щелкнуть каждый цвет, смежный с угловой группой, и записаться.

Реализация алгоритма грубой силы в Javascript требовала десятков миллионов рекурсий, например, 1 и 3 в вопросе, причем время выполнения намного превысило 8-секундный предел. После реализации оптимизаций, описанных выше, пример 1 был решен с помощью всего 38 рекурсий и времени выполнения нескольких миллисекунд. Примеры 2 и 3 были еще более быстрыми.