Сделай ход на доске Го

13

Вам предоставляется позиция на доске для игры в Го и ход для игры. Вам необходимо указать, является ли ход законным или нет, и новую позицию на доске, если это законно.

Краткое объяснение ходов Го: игра состоит в альтернативном размещении черно-белых фигур («камней») в пустых местах на квадратной доске. Наборы кусочков одного цвета, которые соединены друг с другом (4-сторонние), называются группами. Пустые места на доске, прилегающие к группе (также 4-сторонние), считаются «свободами» этой группы. Группа с 0 свободами захватывается (удаляется с доски). Ход, который привел бы к захвату его собственной группы («самоубийство»), является незаконным, если только он не захватывает одну или несколько групп противника (получая свободу в процессе, поэтому он фактически не захвачен).

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

Входные данные: число n от 2 до 19 (включительно), представляющее размер доски, за которым следуют n строк из n чисел от 0 до 2 (включительно), представляющих позицию доски, за которыми следуют 3 числа, разделенные пробелом, представляющие ход, который необходимо сделать. В позиции на доске 0 означает пустое место, 1 означает черный камень и 2 означает белый камень. Движение дает столбец, ряд и цвет (1 или 2) камня для размещения. Столбец и строка основаны на 0, в диапазоне от 0 до n-1 (включительно) и считаются в том же порядке, что и вход платы.

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

Вывод: строка, содержащая 1 или 0 (или true / false, если вы предпочитаете), если ход разрешен или нет, за которым следует (только в случае допустимого перемещения) новая позиция на доске в том же формате, что и вход.

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

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

Примеры:

1) Input:

2
10
01
1 0 2

Output:

0

2) Input:

2
10
11
1 0 2

Output:

1
02
00

3) Input:

5
22122
22021
11211
02120
00120
2 1 1

Output:

1
00100
00101
11011
02120
00120

4) Input:

6
000000
011221
121121
122221
011110
000000
4 0 1

Output:

1
000010
011221
121121
122221
011110
000000
уйти, потому что SE это зло
источник

Ответы:

2

Python 3 (557 504 488)

import sys
s=sys.stdin
M=int(next(s))+1
j=Z=M*M-M
S=s.read(Z)
P=0
b=[0]*3
while j>0:j-=1+(j%M<1);b[int(S[j])]|=1<<j;P|=1<<j
N=lambda x:(x<<1|x>>1|x<<M|x>>M)&P&~x
def h(a,b):t=a|N(a)&b;return h(t,b)if t!=a else a
c,r,m=map(int,next(s).split())
o=m%2+1
p=1<<M*r+c
b[m]|=p
for n in(p<<1,p>>1,p<<M,p>>M):
 e=h(n&P,b[o])
 if~b[m]&N(e)<1<=n&b[o]:b[o]&=~e
_,B,W=b
g=~b[o]&N(h(p,b[m]))>=1>~_&p
print(+g)
q=''
while j<Z:
 r=1<<j
 if g*j%M>M-2:print(q);q=''
 else:q+='012E'[(r&B>0)+(r&W>0)*2]
 j+=1

Использует 3 битовых поля для представления доски - по одному для черного, белого и пустого пространства. Делает поиск соседей Nи цепных hопераций очень лаконичным.

Версия без золота с множеством комментариев: https://gist.github.com/airfrog/8429006

airfrog
источник
У вас есть МНОГО пробелов в конце каждой строки, файл , как вы вывесили он имеет 2732 байт.
Адицу ушел, потому что SE зла
@aditsu Это должно быть исправлено
airfrog
Размер все еще неправильный, сейчас должно быть 555. :) Интересно, можно ли еще сохранить несколько байтов, используя больше точек с запятой?
Адицу ушел, потому что SE зла
Ошибка? Вход: 6 000000 011221 121121 122221 011110 000000 4 0 1Выход: 0. Добавлен теперь как пример 4.
aditsu выход, потому что SE - ЗЛО
Эта ошибка исправлена, я также нашел и исправил еще одну ошибку во время игры в гольф, которую вы можете добавить в качестве примера. Вход: 5 22100 20211 12211 12120 01120 1 1 2выходной сигнал должен быть 0.
airfrog
2

Python ( 912 1004)

def o():
 n=int(raw_input(''))
 i=[raw_input('') for r in range(n+1)]
 b=[map(int,list(r)) for r in i[:n]]
 u,v,w=map(int,i[n].split(' '))
 if b[v][u]!=0:return 0
 b[v][u]=w
 if w==1:q=2
 elif w==2:q=1
 else:return 0
 f=[[],[],[]]
 h=[[],[],[]]
 g=[range(z*n,(z+1)*n) for z in range(n)]
 d=[(1,0),(-1,0),(0,1),(0,-1)]
 m=lambda z:max(0,min(n-1,z))
 t=[0,1,2,0,1]
 for j,s in enumerate(t):
  for r in range(n):
   for c in range(n):
    for y,x in map(lambda p:(m(r+p[0]),m(c+p[1])),d):
     if s==0:
      if b[y][x]==b[r][c]:
       if g[y][x]!=min(g[y][x],g[r][c]):
        t.insert(j+1,0)
       g[y][x]=g[r][c]=min(g[y][x],g[r][c])
     elif s==1:
      if g[r][c] not in h[b[r][c]]:
       h[b[r][c]].append(g[r][c])
      if b[y][x]==0 and g[r][c] not in f[b[r][c]]:
       f[b[r][c]].append(g[r][c])
    if s==2:
     if b[r][c]==q and g[r][c] not in f[b[r][c]]:
      b[r][c]=0
 h[w].sort()
 f[w].sort()
 if h[w]!=f[w]:return 0
 return "1\n"+'\n'.join([''.join(map(str,r)) for r in b])
print o()

Обход: проанализируйте ввод, проверьте, находится ли движение в пустом месте, сделайте ход, инициируйте сетку «группа», упростите / минимизируйте сетку группы, проверив цвет смежных камней (s = 0) и продолжайте повторять, пока он не будет полностью свернут , проверьте для групповых свобод (s = 1) удалите камни противника для групп без свобод (s = 2), повторите s = 0 и s = 1, проверьте, что все группы игроков имеют свободы, верните результат.

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

Интерактивный пример запускает:

2
10
01
1 0 2
0

2
10
11
1 0 2
1
02
00

5
22122
22021
11211
02120
00120
2 1 1
1
00100
00101
11011
02120
00120

6
000000
011221
121121
122221
011110
000000
4 0 1
1
000010
011221
121121
122221
011110
000000
юр
источник
1
Ваша программа ничего не делает, она только определяет функцию.
Адицу ушел, потому что SE это ЗЛО
Запустите его в интерактивном режиме и вызовите его с помощью print o (), как показано в примере run ...
jur
Нет. Предполагается, что это отдельная программа, запускаемая из командной строки. Кроме того, это также сделает его короче.
Адицу ушел, потому что SE зла
Исправлено, добавив печати о () в последней строке
юр
Почему бы просто не использовать тело функции (устаревшее)? И я думаю, что вы также провалили недавно добавленный пример 4.
Адицу ушел, потому что SE это ЗЛО