Ответ 1

Алгоритм

Пусть сначала определите N, количество немиллионных ячеек:

N = R * C - M

Простым решением является заполнение области N немиевых ячеек по строкам сверху вниз. Пример для R=5, C=5, M=12:

c....
.....
...**
*****
*****

То есть:

• Всегда начинайте в верхнем левом углу.
• Заполните N / C строки с не-минами сверху вниз.
• Заполните следующую строку с помощью N % C не-мин слева направо.
• Заполните все остальное минами.

Есть только несколько особых случаев, о которых вам нужно заботиться.

Одиночный не-мин

Если N=1, любая конфигурация является правильным решением.

Однострочный или одиночный столбец

Если R=1, просто заполните не-мины N слева направо. Если C=1, заполните N строки одним (не) мином.

Слишком мало не-мин

Если N четное, оно должно быть >= 4.

Если N нечетно, оно должно быть >= 9. Кроме того, R и C должны быть >= 3.

В противном случае нет решения.

Невозможно заполнить первые две строки

Если N четный, и вы не можете заполнить не менее двух строк не-минами, а затем заполните первые две строки N / 2 неминами.

Если N нечетно, и вы не можете заполнить не менее двух строк не-минами, а третью строку - тремя неминимами, затем заполните первые две строки с помощью (N - 3) / 2 non-mines и третьей строки с 3 неминами.

Одиночный не-мин в последней строке

Если N % C = 1, переместите конечную не-шахту из последней полной строки в следующую строку.

Пример для R=5, C=5, M=9:

c....
.....
....*
..***
*****

Резюме

Можно написать алгоритм, который реализует эти правила, и возвращает описание полученного шахтного поля в O(1). Например, рисование сетки занимает O(R*C). Я также написал реализацию в Perl на основе этих идей, которые были приняты судьей Code Jam Judge.

Ответ 2

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

АЛГОРИТМ

Основная идея - начать с сетки, полной мин, и удалить их, начиная с ячейки {0, 0}, до тех пор, пока на доске не будет правильного количества мин.

Очевидно, что должен быть какой-то способ определить, какие мины удалить дальше, и когда невозможно удалить правильное количество мин. Для этого мы можем сохранить int[][], который представляет плату. Каждая ячейка с шахтой содержит -1, а те, у кого нет мины, есть целое число, которое представляет собой число мин, смежных с ячейкой; так же, как и в реальной игре.

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

Например, конфигурация:

c . *
. . *
. . *
* * *

Будет представлен как:

 0  2 -1
 0  3 -1
 2  5 -1
-1 -1 -1

И граница будет содержать ячейки со значениями: 2, 3, 5, 2

При удалении мины стратегия такова:

• Найдите ячейку на границе, которая имеет то же значение, что и оставшееся количество мин для удаления. Поэтому в приведенном выше примере, если бы у нас было еще 5 мин для удаления, были выбраны ячейки со значением 5 на границе.
• Неспособность выбрать самую маленькую пограничную ячейку. Таким образом, любой из 2 в приведенном выше примере.
• Если значение выбранной ячейки больше количества оставшихся мин для удаления, тогда невозможно построить эту плату, поэтому верните false.
• Else удалите все мины, окружающие выбранную пограничную ячейку.
• Повторяйте до тех пор, пока на плате не появится правильное количество мин - ограничения проблемы выполнены.

В java это выглядит так:

// Tries to build a board based on the nMines in the test case
private static boolean buildBoard(TestCase t) throws Exception {
    if (t.nMines >= t.Board.rows() * t.Board.cols()) { 
        return false;
    }
    // Have to remove the cell at 0,0 as the click will go there
    t.Board.removeMine(0, 0);
    while (!t.boardComplete()) {
        Cell c = nextCell(t);
        // If the value of this cell is greater than what we need to remove we can't build a board
        if (t.Board.getCell(c.getRow(), c.getCol()) > t.removalsLeft()) {
            return false;
        }
        t.Board.removeNeighbourMines(c.getRow(), c.getCol());
    }

    return true;
}

// Find frontier cell matching removals left, else pick the smallest valued cell to keep things balanced
private static Cell nextCell(TestCase t) {
    Cell minCell = null;
    int minVal = Integer.MAX_VALUE;
    for (Cell c : t.Board.getFrontier()) {
        int cellVal = t.Board.getCell(c.getRow(), c.getCol());
        if (cellVal == t.removalsLeft()) {
            return c;
        }
        if (cellVal < minVal) {
            minVal = cellVal;
            minCell = c;
        }
    }
    if (minCell == null) {
        throw new NullPointerException("The min cell wasn't set");
    }
    return minCell;
}

ДОКАЗАТЕЛЬСТВО/ИНТУИЦИЯ

Во-первых, плата определяется как действительная, если ее можно решить одним кликом, даже если на плате есть только одна ячейка, где может произойти этот клик. Поэтому для правильной платы все нечелюстные ячейки должны быть смежными с ячейкой со значением 0, если это не так, ячейка определена как недоступная. Это связано с тем, что мы с уверенностью знаем, что все ячейки, смежные с ячейкой 0, не являются минами, поэтому их можно безопасно выявить, и игра будет делать это автоматически для игрока.

Ключевым моментом для этого алгоритма является то, что всегда необходимо удалить все мины, окружающие самую маленькую пограничную ячейку, чтобы сохранить плату в правильном состоянии. Это довольно просто доказать, выставив плату (например, выше) и выбрав ячейку с наименьшим значением (в этом случае верхний правый 2). Если удаляется только одна шахта, плата не будет действительна, она будет находиться в любом из этих двух состояний:

 0  1  1
 0  2 -1
 2  5 -1
-1 -1 -1

или

 0  1 -1
 0  2  2
 2  5 -1
-1 -1 -1

которые имеют недостижимые ячейки.

Итак, теперь верно, что всегда выбирать самую маленькую пограничную ячейку будет держать плату в правильном состоянии, и мой первый инстинкт заключался в том, что продолжение выбора этих ячеек будет проходить через все допустимые состояния, однако это неверно. Это можно проиллюстрировать с помощью тестового примера, такого как 4 4 7 (поэтому имеется 9 немиевых ячеек). Затем рассмотрим следующую плату:

 0  2 -1 -1
 2  5 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

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

 0  2 -1 -1
 0  3 -1 -1
 0  3 -1 -1
 0  2 -1 -1

Это означает, что теперь невозможно удалить только одну шахту, чтобы завершить доску для этого случая. Однако выбор пограничной ячейки, которая соответствует количеству оставшихся мин (если таковая существует), гарантирует, что 5 будет выбрано, что приведет к квадрату 3x3 неминов и правильному решению тестового примера.

В этот момент я решил дать алгоритму попробовать все тестовые примеры в следующем диапазоне:

0 < R < 20
0 < C < 20
0 ≤ M < R * C

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

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

При первоначальном внедрении этого алгоритма я намеревался написать эвристику, которая построила неминную область в квадратной компоновке. Рассмотрение тестового примера 4 4 7 снова приведет к этому:

 0  0  2 -1
 0  1  4 -1
 2  4 -1 -1
-1 -1 -1 -1

обратите внимание на то, как теперь у нас есть 1 на границе, которая обеспечила бы, чтобы конечная ячейка удаляла квадрат, чтобы дать:

c . . *
. . . *
. . . *
* * * *

Это означало бы, что эвристика слегка изменится:

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

Это может быть реализовано путем сохранения очереди FIFO пограничных ячеек, но я быстро понял, что это сложнее, чем кажется на первый взгляд. Это связано с тем, что значения пограничных ячеек взаимозависимы и поэтому необходимо тщательно следить за тем, чтобы коллекция пограничных ячеек находилась в правильном состоянии, а также не использовать значение ячеек в любом виде хэш-значения и т.д. я "Конечно, это можно сделать, но, осознав, что просто добавив лишнюю эвристику для выбора любых ячеек со значениями, равными остальным работам по удалению, это казалось более легким подходом.

Ответ 3

Это мой код. Я решил принять разные случаи, например, если number of rows=1 или number of columns=1 или if number of mines=(r*c)-1 и несколько других случаев.

Позиция на макете для щелчка помещается в a[r-1][c-1] ('0' индексируется) каждый раз.

По этому вопросу я дал несколько неправильных попыток, и каждый раз, когда я продолжал находить новое дело. Я удалил несколько случаев, когда решение невозможно с помощью goto, и дайте ему перейти к концу, где он распечатывается невозможно. Очень простое решение (действительно, можно сказать, что решение грубой силы, поскольку я кодируется для разных случаев, возможно индивидуально). Это текстовый редактор для моего кода. И на github.

Ответ 4

Я использовал поиск с обратным отсчетом, но я мог решить только небольшой ввод.

В основном алгоритм начинается с доски, заполненной минами, и пытается удалить мины таким образом, чтобы первый "click" решал плату. Ловушка заключается в том, что для расширения "click" в другую ячейку расширение будет происходить из другой ячейки, которая должна также очистить все другие соседние ячейки. Иногда, чтобы перейти в другую ячейку, вам нужно будет удалить другие мины и получить меньше мин, чем требуется. Алгоритм будет возвращаться, если он достигнет такого положения.

Может быть, проще сделать противоположное. Начните с пустой доски и добавьте каждую шахту таким образом, чтобы это не помешало "расширению" первоначального щелчка.

Полный код Python приведен ниже:

directions = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1,  -1],  [1, 0],  [1, 1],
]

def solve(R, C, M):
    def neighbors(i, j):
        for di, dj in directions:
            if 0 <= (i + di) < R and 0 <= (j + dj) < C:
                yield (i + di, j + dj)

    def neighbors_to_clear(i, j, board):
        return [(ni, nj) for ni, nj in neighbors(i, j) if board[ni][nj] == "*"]

    def clear_board(order):
        to_clear = R * C - M - 1
        board = [["*" for _ in range(C)] for _ in range(R)]
        for i, j in order:
            board[i][j] = "."
            for ni, nj in neighbors_to_clear(i, j, board):
                to_clear -= 1
                board[ni][nj] = "."
        return board, to_clear

    def search(ci, cj):
        nodes = []
        board = []
        to_clear = 1
        nodes.append((ci, cj, []))
        while nodes and to_clear > 0:
            i, j, order = nodes.pop()
            board, to_clear = clear_board(order)
            neworder = order + [(i, j)]
            if to_clear == 0:
                board[ci][cj] = "c"
                return board
            elif to_clear > 0:
                for ni, nj in neighbors_to_clear(i, j, board):
                    board[ni][nj] = "."
                    nodes.append([ni, nj, neworder])

    for i in range(R):
        for j in range(C):
            board = search(i, j)
            if board:
                for row in board:
                    print "".join(row)
                return

    print "Impossible"
    return

T = int(raw_input())
for i in range(1, T + 1):
    R, C, M = map(int, raw_input().split(" "))
    print("Case #%d:" % i)
    solve(R, C, M)

Ответ 5

моя стратегия была очень похожа на вашу, и я прошел как маленький, так и большой. Вы думали о случаях ниже?

• R * C - M = 1

• Существует только одна строка

• Есть только две строки

Я перевернул R и C, когда R > C.

Ответ 6

Я разделил это на два начальных частных случая, затем имел общий алгоритм. Версия tl; dr состоит в том, чтобы построить квадрат пустых пространств в левом верхнем углу. Подобно другим ответам, но с меньшим количеством особых случаев.

Специальные случаи

Случай 1

Только 1 пустое место. Просто нажмите в верхнем левом углу и закончите.

Случай 2

2 или 3 пробела, с сеткой, которая не является либо Rx1, либо 1xC. Это невозможно, поэтому нам не удается рано.

Алгоритм

Всегда щелкните в левом верхнем углу. Начните с чистого квадрата 2x2 в левом верхнем углу (у нас есть как минимум 4 пробела). Теперь нам нужно добавить оставшиеся пробелы. Затем мы разберем квадрат вдоль одного края, а затем другого, пока у нас не будет больше пробелов.

Пример порядка гашения:

C  2  6 12
1  3  7 13
4  5  8 14
9 10 11 15

Невозможный случай

Обратите внимание, что при начале нового края мы должны поместить как минимум два пробела, чтобы это было допустимо. Поэтому, если у нас есть только один пробел, это должно быть недействительным (если наш край не имеет длины один). Моя логика выглядела так:

if maxEdgeLength > 1 and remainingBlanks == 1:
    print('Impossible')
    return

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

Моя логика для этого особого случая выглядела так:

if remainingBlanks == 1 and lastEdgeSize > 2:
    mineMatrix[lastBlank] = '*'
    blanks += 1

Ответ 7

Код z сам пояснительный с комментариями. О (г + с)

import java.util.Scanner;
    public class Minesweeper {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            for(int j=0;j<n;j++) {
                int r =sc.nextInt(),
                    c = sc.nextInt(),
                    m=sc.nextInt();
                //handling for only one space.
                if(r*c-m==1) {
                    System.out.println("Case #"+(int)(j+1)+":");
                    String a[][] = new String[r][c];
                    completeFill(a,r-1,c-1,"*");
                    printAll(a, r-1, c-1);
                }
                //handling for 2 rows or cols if num of mines - r*c < 2 not possible.
                //missed here the handling of one mine.
                else if(r<2||c<2) {
                    if(((r*c) - m) <2) {
                        System.out.println("Case #"+(int)(j+1)+":");
                        System.out.println("Impossible");
                    }
                    else {
                        System.out.println("Case #"+(int)(j+1)+":");
                        draw(r,c,m);
                    }
                }
                //for all remaining cases r*c - <4 as the click box needs to be zero to propagate
                else if(((r*c) - m) <4) {
                    System.out.println("Case #"+(int)(j+1)+":");
                    System.out.println("Impossible");
                }
                //edge cases found during execution.
                //row or col =2 and m=1 then not possible.
                //row==3 and col==3 and m==2 not possible.
                else {
                    System.out.println("Case #"+(int)(j+1)+":");
                    if(r==3&&m==2&&c==3|| r==2&&m==1 || c==2&&m==1) {
                        System.out.println("Impossible");
                    }
                    else {
                        draw(r,c,m);
                    }
                }
            }
        }
        /*ALGO : IF m < (r and c) then reduce r or c which ever z max 
         * by two first time then on reduce by factor 1. 
         * Then give the input to filling (squarefill) function which files max one line 
         * with given input. and returns the vals of remaining rows and cols.
         * checking the r,c==2 and r,c==3 edge cases.
         **/
        public static void draw(int r,int c, int m) {
            String a[][] = new String[r][c];
            int norow=r-1,nocol=c-1;
            completeFill(a,norow,nocol,".");
            int startR=0,startC=0;
            int red = 2;
            norow = r;
            nocol = c;
            int row=r,col=c;
            boolean first = true;
            boolean print =true;
            while(m>0&&norow>0&&nocol>0) {
                if(m<norow&&m<nocol) {
                    if(norow>nocol) {
                        norow=norow-red;
                        //startR = startR + red;
                    }
                    else if(norow<nocol){
                        nocol=nocol-red;
                        //startC = startC + red;
                    }
                    else {
                        if(r>c) {
                            norow=norow-red;
                        }
                        else {
                            nocol=nocol-red;
                        }
                    }
                    red=1;
                }
                else {
                    int[] temp = squareFill(a, norow, nocol, startR, startC, m,row,col,first);
                    norow = temp[0];
                    nocol = temp[1];
                    startR =r- temp[0];
                    startC =c -temp[1];
                    row = temp[3];
                    col = temp[4];
                    m = temp[2];
                    red=2;
                    //System.out.println(norow + " "+ nocol+ " "+m);
                    if(norow==3&&nocol==3&&m==2 || norow==2&&m==1 || nocol==2&&m==1) {
                        print =false;
                        System.out.println("Impossible");
                        break;
                    }
                }
                first = false;
            }
            //rectFill(a, 1, r, 1, c);
            if(print)
                printAll(a, r-1, c-1);
        }
        public static void completeFill(String[][] a,int row,int col,String x) {
            for(int i=0;i<=row;i++) {
                for(int j=0;j<=col;j++) {
                    a[i][j] = x;
                }
            }
            a[row][col] = "c";
        }
        public static void printAll(String[][] a,int row,int col) {
            for(int i=0;i<=row;i++) {
                for(int j=0;j<=col;j++) {
                    System.out.print(a[i][j]);
                }
                System.out.println();
            }
        }
        public static int[] squareFill(String[][] a,int norow,int nocol,int startR,int startC,int m,int r, int c, boolean first) {
            if(norow < nocol) {
                int fil = 1;
                m = m - norow;
                for(int i=startR;i<startR+norow;i++) {
                    for(int j=startC;j<startC+fil;j++) {
                        a[i][j] = "*";
                    }
                }
                nocol= nocol-fil;
                c = nocol;
                norow = r;
            }
            else {
                int fil = 1;
                m = m-nocol;
                for(int i=startR;i<startR+fil;i++) {
                    for(int j=startC;j<startC+nocol;j++) {
                        a[i][j] = "*";
                    }
                }
                norow = norow-fil;
                r= norow;
                nocol = c;
            }
            return new int[] {norow,nocol,m,r,c};
        }
    }

Ответ 8

Мой подход к этой проблеме был следующим:

• Для сетки 1x1 M должен быть равен нулю, иначе это невозможно
• Для сетки Rx1 или 1xC нам нужно M <= R * C - 2 (поместите 'c' в последнюю ячейку с пустой ячейкой рядом с ней)
• Для сетки RxC нам нужно M <= R * C - 4 (поместите 'c' на угол с тремя пустыми ячейками вокруг него)

Таким образом, c всегда будет рядом с ним не-минные ячейки независимо от того, что в противном случае невозможно. Это решение имеет смысл для меня, и я проверил выходные данные по их образцу и малым входам, однако он не был принят.

Вот мой код:

import sys

fname = sys.argv[1]

handler = open(fname, "r")
lines = [line.strip() for line in handler]

testcases_count = int(lines.pop(0))

def generate_config(R, C, M):
    mines = M

    config = []
    for row in range(1, R+1):
        if mines >= C:
            if row >= R - 1:
                config.append(''.join(['*' * (C - 2), '.' * 2]))
                mines = mines - C + 2
            else:
                config.append(''.join('*' * C))
                mines = mines - C
        elif mines > 0:
            if row == R - 1 and mines >= C - 2:
                partial_mines = min(mines, C - 2)
                config.append(''.join(['*' * partial_mines, '.' * (C - partial_mines)]))
                mines = mines - partial_mines
            else:
                config.append(''.join(['*' * mines, '.' * (C - mines)]))
                mines = 0
        else:
            config.append(''.join('.' * C))

    # click the last empty cell
    config[-1] = ''.join([config[-1][:-1], 'c'])

    return config

for case in range(testcases_count):
    R, C, M = map(int, lines.pop(0).split(' '))

    # for a 1x1 grid, M has to be zero
    # for a Rx1 or 1xC grid, we must have M <= # of cells - 2
    # for others, we need at least 4 empty cells
    config_possible = (R == 1 and C == 1 and M==0) or ((R == 1 or C == 1) and M <= R * C - 2) or (R > 1 and C > 1 and M <= R * C - 4)

    config = generate_config(R, C, M) if config_possible else None

    print "Case #%d:" % (case+1)
    if config:
        for line in config: print line
    else:
        print "Impossible"

handler.close()

Он работал очень хорошо против своего образца на веб-сайте и против небольшого ввода, который они предоставили, но похоже, что я что-то пропустил.

Вот результат вывода:

Case #1:
Impossible
Case #2:
*
.
c
Case #3:
Impossible
Case #4:
***....
.......
.......
......c
Case #5:
**********
**********
**********
**********
**********
**********
**********
**********
**........
.........c

Обновление: Чтение редакционной статьи vinaykumar, я понимаю, что неправильно с моим решением. Основные правила тральщика, которые я должен был покрыть, в значительной степени.

Ответ 9

Предварительные проверки

M = (R * C) - 1

Заполните сетку всеми минами и нажмите на нее в любом месте.

R == 1 || C == 1

Заполните влево/вправо (или вверх/вниз) по порядку: клик, не-мины, мины (например, c...****).

M == (R * C) - 2 || M == (R * C) - 3

невыполнима

Алгоритм

Я начал с "пустой" сетки (все . s) и поместил клик в угол (я буду использовать левый верхний угол для щелчка и начинаю заполнять мины из нижнего правого).
Мы будем использовать R1 и C1 как наши "текущие" строки и столбцы.

Пока у нас достаточно мин, чтобы заполнить строку или столбец, который при удалении не оставляет ни одной строки или столбца слева (while((M >= R1 && C1 > 2) || (M >= C1 && R1 > 2))), мы "обрезаем" сетку (заполняем минами и уменьшаем R1 или C1), используя самую короткую сторону и удаляем это много мин. Таким образом, 4x5 с 6 минутами осталось бы 4x4 с 2 минутами слева.

• Если в итоге получится 2 x n сетка, мы либо будем иметь 0 мин (мы закончили), либо 1 минута слева (невозможно выиграть).
• Если мы закончим с сеткой 3 x 3, то у нас либо будет 0 мин (мы закончили), 1 мой (продолжить ниже), либо 2 мин (невозможно выиграть).
• Любая другая комбинация является выигрышной. Мы проверяем, есть ли M == min(R1,C1)-1, поэтому нам нужно будет поместить одну шахту в одну строку или столбец из кратчайшего края, а затем заполнить самый короткий край оставшимися минами.

Пример

Я покажу порядок, когда я ввожу мины в сетку с числами, чтобы помочь с визуализацией
R = 7, C = 6, M = 29

c...42
....42
...742
..6742
555542
333332
111111  

Мне потребовалось несколько разных попыток, чтобы мой алгоритм был правильным, но я написал свою книгу на PHP и получил как небольшие, так и большие правильные.

Ответ 10

Решение можно найти здесь. Содержание страницы ниже.

Существует множество способов создания правильной конфигурации шахт. В этом анализа, мы пытаемся перечислить все возможные случаи и попытаемся создать допустимая конфигурация для каждого случая (если существует). Позже, после некоторые идеи, мы обеспечиваем более простой алгоритм для генерации действительная конфигурация шахт (если существует).

Перечисление всех возможных случаев

Начнем с проверки тривиальных случаев:

Если есть только одна пустая ячейка, мы можем просто заполнить все ячейки мины, за исключением ячейки, в которую вы нажимаете. Если R = 1 или C = 1, мины могут быть помещены слева направо или сверху вниз соответственно и нажмите на правую или нижнюю часть ячейки соответственно. Если доска не находится в двух тривиальных случаях выше, это означает, что доска имеет менее 2 х 2. Затем мы можем вручную проверить, что:

Если количество пустых ячеек равно 2 или 3, невозможно, чтобы действительная конфигурация. Если R = 2 или C = 2, существуют допустимые конфигурации только если М четно. Например, если R = 2, C = 7 и M = 5, это Невозможно, так как M нечетно. Однако, если M = 6, мы можем разместить мины в левой части доски и нажмите на нижнюю правую это:              *....             *... c Если на плате нет ни одного из вышеуказанных случаев, это означает, что плата имеет размер не менее 3 х 3. В этом случае мы всегда можем найти правильную конфигурацию шахт, если количество пустых ячеек больше чем 9. Вот один из способов сделать это:

Если количество пустых ячеек равно или больше 3 * C, то мины могут размещаться по строкам сверху вниз. Если количество оставшихся мин может полностью заполнить строку или меньше C - 2 затем поместите мины слева направо в этой строке. В противном случае количество оставшихся мин будет точно C - 1, поместите последнюю шахту в следующую строку. Например:             ****** ******             *****. ****..             ...... → *.....             ............             ..... c..... c Если количество пустых ячеек меньше 3 * C, но не менее 9, мы сначала заполняем все строки минами, кроме последние 3 строки. За последние 3 строки мы заполняем оставшиеся мины колонку по столбцу слева от колонки. Если оставшиеся мины на последний столбец равен двум, затем последний мой должен быть помещен в следующий столбец. Например:             ****** ******              .... → *...             **.... *.....             *.... c *.... c Теперь мы оставляем не более 9 пустых ячеек, которые расположены в ячейках размером 3 x 3 в правом нижнем углу угол. В этом случае мы можем вручную проверить, что если число пустых Ячейки 5 или 7, Невозможно иметь действительную конфигурацию шахты. В противном случае мы можем жестко закодировать правильную конфигурацию для каждого номера пустая ячейка в 3 × 3 квадратных ячейках.

Вздох... это было много случаев, чтобы покрыть! Как мы убеждаем себя что, когда мы закодируем решение, мы не пропустим ни одного углового случая?

Метод грубой силы

Для небольшого ввода размер платы составляет не более 5 х 5. Мы можем проверить все (25 выберите M) возможные конфигурации шахт и найдите тот, который действителен (то есть, щелкая пустую ячейку в конфигурации, обнаруживают все остальные пустые ячейки). Чтобы проверить правильность конфигурации шахты, мы можем запустить алгоритм заполнения заливки (или простой поиск с первого дыхания) из щелкнула пустую ячейку и проверила, что все остальные пустые ячейки доступны (то есть они находятся в одной компоненте связи). Обратите внимание, что мы также должны проверьте все возможные позиции кликов. Этот подход грубой силы выполняется быстро достаточно для небольшого ввода.

Подход грубой силы можно использовать для проверки (при малых значениях R, C, M) есть ли ложная ошибка в нашей стратегии перечисления выше. Фальшиво-отрицательный результат обнаруживается, когда существует действующая шахта конфигурации, но вышеперечисленная стратегия перечисления не дает возможности. Как только мы уверены, что наша стратегия перечисления не производит любой ложноотрицательный, мы можем использовать его для решения большого ввода.

Более простой в использовании подход

После игры с несколькими действующими шахтными конфигурациями, используя перечислительной стратегии выше, вы можете заметить шаблон: в действительном шахте конфигурации, количество мин в определенной строке всегда равно или больше, чем количество шахт строк под ним, и все мины выравниваются по левому краю подряд. С этим пониманием мы можем реализовать более простой алгоритм обратного отслеживания, который помещает мины по строкам сверху к нижней части с не увеличивающимся количеством мин, когда мы переходим к заполнению следующая строка и обрезка, если конфигурация для текущей строки недействителен (его можно проверить, щелкнув в нижней правой ячейке). Эта откат с обрезкой может обрабатывать до 50 x 50 размеров платы в разумное время и проще реализовать (т.е. нет необходимости перечислить угловые/хитрые случаи).

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

Ответ 11

Я тоже попробовал удачу в этом вопросе, но почему-то не прошел проверки.

Я решил, что он разрешим для (матрица 3x3), если есть меньше (строк * cols-4) мины, так как мне нужны только 4 ячейки для "c" и ее границы как "."

Могут быть мои алгоритмы:

Решаемые:

• Проверяет, достаточно ли места для шахт (rows*cols - 4 == maximum mines)
• Исключения, такие как rows == 1, cols == 1; то он строит * cols-2
• Условное, возможное или невозможное

Создать решение

• Построить rows*cols matrix, со значением по умолчанию nil
• Перейдите к m[0][0] и назначьте 'c'
• Определите окружение m[0][0] с помощью '.'
• Петля справа от матрицы и присвойте '*', пока мины не закончатся, затем назначьте '.'