Hitung Poligon Tertutup

8

Memasukkan:

Sebuah NxMjaringan atau multi-string line (atau wajar input-format lain), yang berisi hanya dicetak ASCII (kisaran unicode [32,126]).

Keluaran:

Jumlah poligon tertutup dengan karakter yang sama yang dapat ditemukan, dengan dua aturan khusus:

  • Spasi adalah wildcard dan dapat digunakan (beberapa kali) untuk karakter apa pun
  • o,, Odan 0dihitung sebagai poligon tertutup sendiri

Aturan tantangan:

  • (Anti-) Koneksi diagonal antara karakter (atau spasi) yang sama dimasukkan untuk membentuk poligon tertutup.
  • Anda tidak dapat membahas karakter lain (kecuali ruang wild-card). (Yaitu dalam kasus uji pertama / contoh di bawah ini, Anda tidak dapat membentuk dua segitiga dengan tanda A's dengan melewati x.) Jadi semua karakter yang digunakan untuk poligon tertutup harus terhubung (horizontal, vertikal, dan / atau (anti-) secara diagonal ).
  • Poligon setidaknya tiga karakter (termasuk karakter tunggal o, O, 0).
  • Garis-garis karakter yang berdekatan bukan poligon tertutup.
  • Karakter yang sama tidak dapat digunakan untuk beberapa poligon, tidak termasuk ruang wildcard.
  • Ruang wildcard tidak dapat dihitung sebagai o, O, atau 0.
  • Tiga atau lebih spasi saja tidak dapat membentuk poligon tertutup. Itu harus selalu memiliki setidaknya satu karakter non-spasi (dan non o/ O/ 0).
  • Input dapat dalam format apa pun yang masuk akal. Dapat berupa karakter-matriks, string pembatas baris baru, string-array, karakter-array dengan penambahan bilangan bulat, dll.
  • Input akan selalu menjadi persegi panjang N oleh M (atau persegi), jadi tidak ada bentuk input yang aneh
  • Karena karakter yang sama tidak dapat digunakan lebih dari sekali dan kami ingin memiliki banyak poligon tertutup, menggunakan beberapa karakter untuk membentuk dua (atau lebih) poligon tertutup, bukan satu poligon yang lebih besar tentu saja tujuan yang dimaksudkan dalam penghitungan (yang juga merupakan mengapa poligon tertutup dibentuk oleh o,, Oatau 0tidak akan pernah dihitung, karena mereka sudah tertutup poligon secara terpisah).
  • Huruf besar dan huruf kecil tentu saja dihitung sebagai karakter individu.

Aturan umum:

  • Ini adalah , jadi jawaban tersingkat dalam byte menang.
    Jangan biarkan bahasa kode-golf mencegah Anda memposting jawaban dengan bahasa non-codegolf. Cobalah untuk memberikan jawaban sesingkat mungkin untuk bahasa pemrograman 'apa pun'.
  • Aturan standar berlaku untuk jawaban Anda dengan aturan I / O default , sehingga Anda diizinkan untuk menggunakan STDIN / STDOUT, fungsi / metode dengan parameter yang tepat dan tipe pengembalian, program penuh. Panggilanmu.
  • Celah default tidak diperbolehkan.
  • Jika memungkinkan, silakan tambahkan tautan dengan tes untuk kode Anda (yaitu TIO ).
  • Juga, menambahkan penjelasan untuk jawaban Anda sangat dianjurkan.

Contoh / Kasus Uji:

Memasukkan:

AAAw
AxA4
'AoQ

Output:, 2karena poligon ini dapat dibentuk:
masukkan deskripsi gambar di sini


Memasukkan:

1822uaslkoo
12*2sl ljoo
a* 0a91)j$*
()*#J9dddj*
*Q#ID dJj!"
*UJD SO&*93

Output:, 12karena poligon ini dapat dibentuk:
masukkan deskripsi gambar di sini

Perhatikan bahwa:
- Yang kuning di bawah ini bukan poligon, karena osudah dihitung sebagai poligon yang terpisah
- Yang ungu dan coklat tidak tertutup
- Yang merah, abu-abu, hijau, dan biru muda menggunakan satu atau lebih non karakter spasi-yang sudah digunakan untuk poligon tertutup lainnya
masukkan deskripsi gambar di sini


Input (dimensi 2x4):

3  3
  2 

Output:, 3karena poligon ini dapat dibentuk:
masukkan deskripsi gambar di sini


Memasukkan:

AAAA
AAAA
AAxA

Output:, 3karena poligon ini dapat dibentuk:
masukkan deskripsi gambar di sini

Tentu saja poligon lain dimungkinkan di sini, tetapi tidak lebih dari 3. Berikut contoh lain yang valid dengan 3poligon:
masukkan deskripsi gambar di sini


Memasukkan:

0QoO

Output:, 3karena poligon ini dapat dibentuk:
masukkan deskripsi gambar di sini


Memasukkan:

W w
 Ww

Output:, 3karena poligon ini dapat dibentuk:
masukkan deskripsi gambar di sini

Perhatikan bahwa ruang lapisan atas digunakan untuk ketiga poligon. Berikut adalah tiga poligon yang disorot secara individual:
masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini


Memasukkan:

W W
 WW

Keluaran:, 3karena tiga poligon yang sama seperti pada tes sebelumnya dapat dibentuk. Jadi tidak, tidak 2dengan dua poligon ini:
masukkan deskripsi gambar di sini


Memasukkan:

abcdQefg
hQiQjQQk
QlQmnopQ
QqrstQQu
QvQQQwxy
QQz0QQQQ

Output:, 3karena poligon ini dapat dibentuk:
masukkan deskripsi gambar di sini

Kevin Cruijssen
sumber
2
Saya ingin untuk +1ini, tetapi saya benar-benar tidak melihat apa khusus casing os, Os & 0s menambah tantangan.
Shaggy
Sepertinya semua contoh poligon adalah cembung. Kecuali jika poligon cekung dikecualikan, saya sarankan untuk menambahkan test case termasuk satu.
Arnauld
1
@Arnauld Menambahkan test case di bagian bawah. Tidak yakin apakah itu cukup untuk apa yang Anda maksudkan, karena itu hanya masuk sekali. Grid harus cukup besar untuk membuat poligon cekung. Jika Anda memiliki test case yang disarankan yang harus saya tambahkan sebagai tambahan, beri tahu saya.
Kevin Cruijssen
@ Shaggy Anda agak benar. Ketika saya membuat tantangan saya melihat bentuk o, O, 0menjadi lingkaran sebagai poligon individu, tetapi solusi itu tidak menambahkan banyak, kecuali bahwa o, O, 0harus dihindari ketika membentuk poligon yang lebih besar, dan menambahkan hitungan bagi mereka. Terlambat untuk mengubahnya sekarang.
Kevin Cruijssen

Jawaban:

4

Python 2 , 714 737 821 byte

  • -23 byte, terima kasih kepada Kevin Cruijssen
M=input()
m=''.join(M)
def P(L):
 if len(L)<2:yield[L];return
 for p in P(L[1:]):
	for n,s in enumerate(p):yield p[:n]+[[L[0]]+s]+p[n+1:]
	yield[[L[0]]]+p
h,w,R,C=len(M),len(M[0]),0,[-1,0,1]
K=[(i,j)for i in range(h)for j in range(w)]
Z=[(i,j)for i,j in K if' '==M[i][j]]
from networkx import*
for l in set(m):
 G,S=[],[]
 if l in'oO0':R+=m.count(l);continue
 for I in K:
  i,j=I
  for p in C:
	for q in C:
	 X=x,y=i+p,j+q
	 if X in K and X!=I and set(M[i][j]+M[x][y])<=set(' '+l):G+=[(I,X)];S+=[I,X]
 B=0
 for L in P(list(set(S))):
  b=0
  for p in L:
	for i,j in p:
	 if' '!=M[i][j]: 
		try:find_cycle(from_edgelist([(I,X)for I,X in G if I in p+Z and X in p+Z]));b+=1
		except:1
		break
	if b>B:B=b
 R+=B
print R

Cobalah online!

  1. Untuk setiap huruf A(kecuali o,, Odan 0) kode membangun grafik yang mewakili kedekatan dari berbagai kejadian huruf Adan ruang dalam matriks awal yang diberikan. Kemudian ia menghitung himpunan siklus semi-terpisah yang menutupi grafik ketika memaksimalkan jumlah siklus (pemisahan hanya didasarkan pada huruf A, ruang yang sama dapat digunakan untuk beberapa siklus).

  2. Kode lulus semua tes.

  3. Input: daftar garis matriks.

  4. Penjelasan lebih lanjut dan golf segera hadir.
mdahmoune
sumber
1
714 byte dengan menggunakan kombinasi tab dan spasi sebagai lekukan, bukan hanya spasi.
Kevin Cruijssen