Bergerak di papan Go

13

Anda diberi posisi dewan untuk permainan Go dan gerakan untuk bermain. Anda perlu menampilkan apakah perpindahan itu sah atau tidak, dan posisi dewan baru jika sah.

Penjelasan singkat tentang gerakan Go: permainan ini terdiri dari menempatkan potongan hitam dan putih ("batu") sebagai alternatif di tempat kosong di papan persegi. Set potongan-potongan dengan warna yang sama yang terhubung satu sama lain (4 arah) disebut kelompok. Tempat kosong di papan yang berdekatan dengan grup (juga 4 arah) dianggap sebagai "kebebasan" grup itu. Grup dengan 0 kebebasan ditangkap (dihapus dari papan). Suatu langkah yang akan menyebabkan kelompoknya sendiri ditangkap ("bunuh diri") adalah ilegal, kecuali jika ia menangkap satu atau lebih kelompok lawan (memperoleh kebebasan dalam proses sehingga tidak benar-benar ditangkap).

Bagi mereka yang berkepentingan, Anda tidak perlu berurusan dengan ko (dan superko), yaitu Anda dapat menganggap penangkapan ko adalah legal. Jika Anda tidak tahu apa artinya itu, cukup ikuti aturan di atas dan itu akan baik-baik saja.

Input: angka n antara 2 dan 19 (inklusif) mewakili ukuran papan, diikuti oleh n baris n angka antara 0 dan 2 (inklusif) mewakili posisi papan, diikuti oleh 3 angka yang dipisahkan oleh spasi, mewakili gerakan untuk membuat. Dalam posisi papan, 0 berarti tempat kosong, 1 berarti batu hitam dan 2 berarti batu putih. Langkah memberi kolom, baris dan warna (1 atau 2) dari batu ke tempat. Kolom dan baris berbasis 0, mulai dari 0 hingga n-1 (inklusif) dan dihitung dalam urutan yang sama dengan input papan.

Anda dapat mengasumsikan bahwa posisi dewan yang diberikan adalah legal (semua grup memiliki setidaknya satu kebebasan).

Keluaran: baris yang mengandung 1 atau 0 (atau benar / salah jika Anda suka) jika perpindahan itu legal atau tidak, diikuti (hanya dalam kasus perpindahan legal) oleh posisi dewan baru dalam format yang sama dengan input.

Nilai: Jumlah byte dari kode sumber lengkap, lebih kecil lebih baik. Denda tambahan 20% untuk penggunaan karakter non-ascii, dan denda tambahan 20% jika kode Anda tidak dapat diuji di Linux menggunakan perangkat lunak yang tersedia secara bebas.

Aturan: Tidak ada koneksi jaringan dan tidak ada perpustakaan pihak ketiga. Program Anda harus menggunakan input standar dan stream output, atau standar yang setara untuk bahasa pemrograman Anda.

Contoh:

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
aditsu berhenti karena SE adalah JAHAT
sumber

Jawaban:

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

Menggunakan 3 bitfield untuk mewakili papan - masing-masing untuk ruang hitam, putih, dan kosong. Buat tetangga yang dapat ditemukan Ndan dapatkan hoperasi berantai dengan sangat ringkas.

Versi ungolfed dengan banyak komentar: https://gist.github.com/airfrog/8429006

airfrog
sumber
Anda memiliki BANYAK ruang di akhir setiap baris, file yang Anda posting memiliki 2732 byte.
Aditsu berhenti karena SE adalah JAHAT
@aditsu Itu harus diperbaiki sekarang
airfrog
Ukurannya masih salah, harus 555 sekarang :) Juga saya ingin tahu apakah Anda masih dapat menyimpan beberapa byte dengan menggunakan lebih banyak titik koma.
Aditsu berhenti karena SE adalah JAHAT
Bug? Input: 6 000000 011221 121121 122221 011110 000000 4 0 1Output: 0. Ditambahkan sekarang sebagai contoh 4.
aditsu berhenti karena SE adalah
Bug itu sudah diperbaiki, saya juga menemukan dan memperbaiki bug lain saat bermain golf yang mungkin ingin Anda tambahkan sebagai contoh. Input: 5 22100 20211 12211 12120 01120 1 1 2Output harus 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()

Berjalanlah melalui: masukan parse, periksa apakah gerakan ada di tempat kosong, buat bergerak, init "grup" grid, sederhanakan / perkecil grid grup dengan memeriksa warna batu adjacant (s = 0) dan terus mengulangi sampai sepenuhnya diperkecil , periksa untuk kebebasan grup (s = 1), hapus batu lawan untuk grup tanpa kebebasan (s = 2), ulangi s = 0 dan s = 1, periksa bahwa semua grup pemain memiliki kebebasan, hasilkan kembali.

Ini mungkin dapat dipersingkat secara signifikan ...

Contoh Interaktif berjalan:

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
jur
sumber
1
Program Anda tidak melakukan apa-apa, itu hanya mendefinisikan suatu fungsi.
Aditsu berhenti karena SE adalah JAHAT
Jalankan secara interaktif dan sebut dengan print o () seperti yang ditunjukkan pada contoh run ...
jur
Nggak. Seharusnya program mandiri yang Anda jalankan dari baris perintah. Selain itu, itu juga akan membuatnya lebih pendek.
Aditsu berhenti karena SE adalah JAHAT
Memperbaikinya dengan menambahkan print o () pada baris terakhir
jur
Mengapa tidak menggunakan fungsi tubuh saja (ketinggalan zaman)? Dan saya pikir Anda juga gagal pada contoh 4. yang baru ditambahkan
aditsu berhenti karena SE adalah