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

Изящный математический факт о сетке Сапер (aka board) таков:

Доска и ее дополнение имеют одинаковое общее количество шахт . ( Доказательство )

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

Например, для сетки Сапер

**1..
34321
*2**1

общее количество мин составляет 1 + 3 + 4 + 3 + 2 + 1 + 2 + 1 = 17.

Дополнение сетки

24***
*****
3*44*

у которого моя общая сумма 2 + 4 + 3 + 4 + 4 = 17 снова.

Напишите программу, которая принимает произвольную сетку Сапер в текстовой форме, где *представляет мину и 1сквозную 8представляет количество мин, примыкающих к ячейке, не относящейся к мине. Вы можете использовать .или 0или (пробел) для представления ячеек без моих соседей, по вашему выбору. Можно предположить, что входная сетка будет правильно помечена, т. Е. Каждая не моя ячейка будет точно обозначать общее количество мин, непосредственно прилегающих к ней ортогонально или по диагонали.

Ваша программа должна напечатать дополнение сетки в том же формате ( с использованием тех же ., 0или , как вы ожидали на входе).

Самый короткий код в байтах побеждает.

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

Тестовые случаи

^{Все входы и выходы можно поменять местами, поскольку дополнением является исходная сетка. Решетки также можно вращать для дальнейших тестовых случаев.}

Входные данные:

111
1*1
111

Выход:

***
*8*
***

Входные данные:

.

Выход:

*

Входные данные:

*11*1.1**1...1***1.....1*****1..........

Выход:

1**2***11*****1.1*******1...1***********

Вход: ( пример Cut The Knot )

**212*32
333*33**
1*22*333
222222*1
*33*2232
2**22*2*

Выход:

24***4**
***7**64
*8**7***
******8*
4**7****
*33**5*3

Pyth, 39 38 байт

j.es.eh-+K\*l-s:RtWYY+Y2:+K.zk+k3KZb.z

Попробуйте онлайн: демонстрация

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

Объяснение:

j.es.eh-+K\*l-s:RtWYY+Y2:+K.zk+k3KZb.z  implicit: .z = list of input strings
 .e                                 .z  map each index k, line b of .z to:
    .e                             b      map each index Y, char Z of b to:
         K\*                                assign "*" to K
                         +K.z               insert K at the front of .z
                        :    k+k3           slice from k to k+3
               :RtWYY+Y2                    take the slice from Y-1 or 0 
                                            to Y+2 for each line
              s                             join, this gives the 3x3 rectangle
                                             (or smaller on the border)
             -                   K          remove all "*"s
            l                               take the length
        +K                                   "*" + ^
       -                          Z         remove Z from this string
      h                                     and take the first char
                                            (if cell=mine take the number, 
                                             otherwise take the number)
  s                                       join the chars of one line
j                                       join by newlines

CJam, 58 57 байт

0WX]2m*qN/{'*f+z}2*f{\~@m<fm<W<}:..+{W<{_'*#'*@'*-,?}/N}/

Ввод не должен заканчиваться переводом строки. Выход содержит 0для клеток без близлежащих мин.

Попробуйте онлайн в интерпретаторе CJam .

идея

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

Для ввода

*4*
**2

это приводит к

*4**
**2*
****

Теперь мы генерируем все возможные модификации, которые приводят к повороту строк и столбцов на 0, -1 или 1 единиц вверх / влево:

*4** **** **2* **4* **** ***2 4*** **** *2**
**2* *4** **** ***2 **4* **** *2** 4*** ****
**** **2* *4** **** ***2 **4* **** *2** 4***

Мы отбрасываем «места заполнения» от каждого поворота, т.е.

*4* *** **2 **4 *** *** 4** *** *2*
**2 *4* *** *** **4 *** *2* 4** ***

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

******4** 4*******2 **24*****
*******4* *4****2** 2***4****

Первым символом каждой позиции является ее оригинальный характер.

• Если это не звездочка, ее следует заменить звездочкой.

• Если это звездочка, то число звездочек в этой строке равно числу соседних мин.

Как это работает

0WX]2m*   e# Push the array of all vectors of {0,-1,1}^2.
qN/       e# Read all input from STDIN and split at linefeeds.
{'*f+z}2* e# Append a '*' to each row and transpose rows with columns. Repeat.
f{        e# For each vector [A B], push the modified input Q; then:
  \~      e#   Swap Q with [A B] and dump A and B on the stack.
  @m<     e#   Rotate the rows of Q B units up.
  fm<     e#   Rotate each row of the result A units left.
  W<      e#   Discard the last row.
}         e# This pushes all nine rotations with Manhattan distance 1.
:..+      e# Concatenate the corresponding characters for each position.
{         e# For each row:
  W<      e#   Discard the character corresponding to the last column.
  {       e#   For each remaining string:
    _'*#  e#     Find the first index of '*' in a copy.
    '*    e#     Push '*'.
    @'*-, e#     Count the non-asterisks in the string.
    ?     e#     Select '*' if the index is non-zero, the count otherwise.
  }/      e#
  N       e#   Push a linefeed.
}/        e#

Руби, 119

->s{w=1+s.index('
')
s.size.times{|c|t=0;9.times{|i|(s+?**w*2)[c+i/3*w-w+i%3-1]<?0||t+=1}
print [t,?*,'
'][s[c]<=>?*]}}

Разгружен в тестовой программе:

f=->s{
  w=1+s.index("\n")                          #width of board
  s.size.times{|c|                           #iterate through input
    t=0;                                     #number of digits surrounding current cell
    9.times{|i|                              #iterate through 3x3 box (centre must be * if this ever gets printed.)
      (s+"*"*w*2)[c+i/3*w-w+i%3-1]<"0"||t+=1 #copy of s has plenty of * appended to avoid index errors
    }                                        #add 1 every time a number is found.
  print [t,"*","\n"][s[c]<=>"*"]             #if * print t. if after * in ACSII it's a number, print *. if before, it's \n, print \n
  }
}


f['**212*32
333*33**
1*22*333
222222*1
*33*2232
2**22*2*']

Октава, 76

m=@(s)char(conv2(b=(cell2mat(strsplit(s)'))~='*',ones(3),'same').*~b-6*b+48)

объяснение

• Преобразуйте входную строку в матрицу строк, используя strsplitи cell2mat.

• Получить логическую матрицу, содержащую, 1где нет *в исходной матрице.

• Возьмите свертку с матрицей 3х3 из 1.

• Замаскируйте его с помощью обратной логической матрицы и поместите *вместо маски.

• Примечание: клетки без моих соседей представлены как 0.

выполнение

>> m(['**100' 10 '34321' 10 '*2**1'])   %// `10` is newline
ans =

24***
*****
3*44*

>> m(['24***' 10 '*****' 10 '3*44*'])
ans =

**100
34321
*2**1