Wprowadzenie

Doświadczeni golfiści przygotowali nas na potop . Obszary zagrożone zostały ewakuowane, a ludność przeniosła się na wyżyny.

Nie doceniliśmy powodzi (a być może wystąpił błąd w kodzie @ user12345). Niektóre obszary położone na dużych obszarach szybko zbliżają się do poziomu morza. Ściany muszą zostać wzniesione, aby zapewnić przetrwanie gęsto zaludnionych obozowisk. Niestety rząd ma ograniczoną podaż ścian.

Problem

Nasz scenariusz zagłady opisany jest dwoma liczbami w jednym wierszu, noraz m. Po tej linii znajdują się nwiersze z mwartościami na wiersz, oddzielone tylko jedną spacją. Każda wartość będzie miała jeden z czterech znaków.

• xNieprzekraczalny. Woda nie może tutaj płynąć. Nie można tutaj wznosić ścian.
• -Nietrwały. Woda może przez to przepływać. Nie można tutaj wznosić ścian.
• .Stabilny. Woda może tutaj przepływać. Można tutaj wznosić ściany.
• oObozowisko. Woda może tutaj przepływać. Jeśli tak, wszyscy umierają. Nie można tutaj budować ścian.

Woda będzie płynąć ze wszystkich krawędzi mapy, chyba że krawędź jest nieprzejezdna lub ściana zostanie zbudowana na kafelku. Napisz program, który może wygenerować minimalną liczbę ścian wymaganą do ochrony obozowiska.

Przykładowe dane wejściowe

 6 7
 x . . x x x x
 x . . x - - x
 x . x x - - x
 x . o o o - .
 x . o o o - .
 x x x x x x x

Przykładowy wynik

3

Założenia

• Woda płynie tylko ortogonalnie
• Obozowiska istnieją tylko jako jeden ciągły prostokątny blok na scenariusz
• Rozwiązanie zawsze będzie istnieć (chociaż może wymagać dużej ilości ścian)
• Obozowiska nie mogą być zlokalizowane na krawędzi, ponieważ wtedy scenariusz nie miałby rozwiązania
• 2 n<<16
• 2 m<<16
• Dane wejściowe można podać ze standardowego wejścia, odczytać z „city.txt” lub zaakceptować jako pojedynczy argument

Najkrótszy kod wygrywa!

Mathematica, 257 253 znaków

d="city.txt"~Import~"Table";g=EdgeAdd[#,∞<->Tr@#&/@Position[VertexDegree@#,2|3]]&@GridGraph@d[[1,{2,1}]];{o,x,s}=Tr/@Position[Join@@d[[2;;]],#]&/@{"o","x","."};Catch@Do[If[Min[GraphDistance[VertexDelete[g,x⋃w],∞,#]&/@o]==∞,Throw@Length@w],{w,Subsets@s}]

Dane wejściowe są odczytywane z "city.txt".

Wyjaśnienie:

Mathematica ma wiele funkcji do obsługi wykresów.

Najpierw czytam dane z "city.txt".

d="city.txt"~Import~"Table";

Następnie tworzę wykres siatki z 'm' * 'n' wierzchołkami ( GridGraph@d[[1,{2,1}]]) i dodam do niego „wierzchołek w nieskończoności”, który jest połączony z każdym wierzchołkiem na „krawędziach” wykresu. Z tego wierzchołka wypływa woda.

g=EdgeAdd[#,∞<->Tr@#&/@Position[VertexDegree@#,2|3]]&@GridGraph@d[[1,{2,1}]];

I o, xi soznaczają pozycje „O”, „X” i „”. odpowiednio.

{o,x,s}=Tr/@Position[Join@@d[[2;;]],#]&/@{"o","x","."};

Następnie dla każdego podzbioru wz s(podzbiory są klasyfikowane według długości), usunąć wierzchołki w xi wz g( VertexDelete[g,x⋃w]), i znaleźć długość najkrótszej ścieżki z wierzchołka „w nieskończoność” do obozowiska o. Jeśli długość wynosi nieskończoność, obozowisko będzie bezpieczne. Tak więc długość pierwszego takiego wjest minimalną liczbą ścian wymaganych do ochrony obozowiska.

Catch@Do[If[Min[GraphDistance[VertexDelete[g,x⋃w],∞,#]&/@o]==∞,Throw@Length@w],{w,Subsets@s}]

C 827 799 522

Gra w golfa:

#define N for(
#define F(W,X,Y,Z) N i= W;i X Y;i Z)
#define C(A,B,C) if(c[A][B]==C)
#define S(W,X,Y,Z,A,B) p=1;F(W,X,Y,Z)C(A,B,120)p=0;if(p){F(W,X,Y,Z){C(A,B,46){c[A][B]='x';z++;Q();break;}}}else{F(W,X,Y,Z){C(A,B,120)break;else c[A][B]='o';}}
p,m,z,w,h,o,i,u,l,x,y;char c[16][16];Q(){N u=0;u<h;u++)N l=0;l<w;l++)if(c[u][l]=='o'){x=u;y=l;S(x,>,m,--,i,y)S(y,>,m,--,x,i)S(y,<,w,++,x,i)S(x,<,h,++,i,y)}}main(int a, char **v){h=atoi(v[1]);w=atoi(v[2]);N m=-1;o<h;o++)N i=0;i<w;i++)scanf("%c",&c[o][i]);Q();printf("%d",z);}

Dane wejściowe są podawane jako argumenty z wysokością i jako jako argumenty wiersza poleceń, a następnie siatka jest odczytywana jako pojedynczy ciąg znaków na standardowym ./a.out 6 7 < inputwejściu, podobnie jak: gdzie dane wejściowe są w tej formie (od lewej do prawej, od góry do dołu):

x..xxxxx..x - xx.xx - xx.ooo-.x.ooo-.xxxxxxx

"Czytelny":

#define F(W,X,Y,Z) for(i= W;i X Y;i Z)
#define C(A,B,C) if(c[A][B]==C)
#define S(W,X,Y,Z,A,B) p=1;F(W,X,Y,Z)C(A,B,120)p=0;if(p){F(W,X,Y,Z){C(A,B,46){c[A][B]='x';z++;Q();break;}}}else{F(W,X,Y,Z){C(A,B,120)break;else c[A][B]='o';}}

/*Example of an expanded "S" macro:
p=1;
for(i=x;i>m;i--) if(c[i][y]==120) p=0;
if(p)
{
    for(i=x;i>m;i--)
    {
        if(c[i][y]==46)
        {
            c[i][y]='x';
            z++;
            Q();
            break;
        }
    }
}
else
{
    for(i= x;i > m;i --)
    {
        if(c[i][y]==120) break;
        else c[i][y]='o';
    }
}
*/

p,m,z,w,h,o,i,u,l,x,y;
char c[16][16];
Q(){
    for(u=0;u<h;u++)
        for(l=0;l<w;l++)
            if(c[u][l]=='o')
            {
        x=u;y=l;
        S(x,>,m,--,i,y)
        S(y,>,m,--,x,i)
        S(y,<,w,++,x,i)
        S(x,<,h,++,i,y)
            }
}

main(int a, char **v)
{
    h=atoi(v[1]);
    w=atoi(v[2]);
    for(m=-1;o<h;o++)
        for(i=0;i<w;i++)
            scanf("%c",&c[o][i]);
    P();
    Q();
    printf("%d\n",z);
    P();
}

//Omitted in golfed version, prints the map.
P()
{
    for(o=0;o<h;o++)
    {
        for (i=0;i<w;i++) printf("%c",c[o][i]);
        printf("\n");
    }   
}

Nigdzie nie jest tak krótkie jak rozwiązanie @Claudiu, ale działa niesamowicie szybko. Zamiast zalewać brzegi, znajduje obozowisko i działa na zewnątrz z tokenów „o”.

• Jeśli napotka jakiekolwiek niestabilne podłoże obok obozowiska, rozszerza obozowisko na niego.
• Jeśli jakiekolwiek obozowisko na siatce nie ma co najmniej jednej ściany w każdym kierunku, porusza się w tym kierunku, dopóki nie zbuduje ściany.
• Po umieszczeniu każdej nowej sekcji ściany powtarza się, aby znaleźć następną sekcję ściany do umieszczenia.

Przykładowe miejsca na ścianie:

x..xxxx                           x..xxxx
x..x--x                           x..xoox
x.xx--x                           x3xxoox
x.ooo-.  <-- results in this -->  xooooo1
x.ooo-.                           xooooo2
xxxxxxx                           xxxxxxx

Python, 553 525 512 449 414 404 387 368 znaków (+4? Do wywołania)

Miałem za dużo zabawy w golfa. Jest 82 bajtów większy, jeśli spróbujesz go skompresować! Teraz jest to miara zwartości i braku powtarzalności.

R=range;import itertools as I
f=map(str.split,open('city.txt'))[1:]
S=[]
def D(q):
 q=set(q)
 def C(*a):
    r,c=a
    try:p=(f[r][c],'x')[a in q]
    except:p='x'
    q.add(a)
    if'.'==p:S[:0]=[a]
    return p<'/'and C(r+1,c)|C(r-1,c)|C(r,c+1)|C(r,c-1)or'o'==p
 if sum(C(j,0)|C(j,-1)|C(0,j)|C(-1,j)for j in R(16))<1:print n;B
D(S);Z=S[:]
for n in R(len(Z)):map(D,I.combinations(Z,n))

Poziomy wcięcia to spacja, tab.

Zastosowanie :

Czyta z city.txt:

6 7
x . . x x x x
x . . x - - x
x . x x - - x
x . o o o - .
x . o o o - .
x x x x x x x

Wywołaj w następujący sposób:

$ python floodfill_golf.py 2>X
3

Ma 2>Xto na celu ukrycie stderr, ponieważ program kończy działanie, zgłaszając wyjątek. Jeśli zostanie to uznane za niesprawiedliwe, dodaj 4 znaki do wywołania.

Objaśnienie :

Prosta brutalna siła. Cwykonuje zalanie i zwraca wartość true, jeśli trafi na obozowisko. Bez dodatkowych wypełnień, ponieważ prawidłowe ustawienie wypełnienia zajęło zbyt dużo miejsca. D, biorąc pod uwagę zestaw ścian do wypełnienia, wzywa Cz każdego punktu na krawędzi, tak że Cuwzględnia te ściany, drukuje długość i wychodzi, jeśli żaden z nich nie dotrze do obozowiska. Lista ścian służy również do śledzenia zalania, więc nie jest wymagane kopiowanie planszy! Zręcznie, Cdołącza również wszystkie znalezione puste miejsca do listy, Swięc funkcja Dsłuży również do konstruowania listy pustych miejsc. Z tego powodu używam sumzamiast any, aby upewnić się, że wszystkie .s są zbierane przy pierwszym uruchomieniu.

Wzywam Djeden raz, a następnie skopiować listę pustych miejsc do Zponieważ Szachowa dołączany (nieefektywne, ale tańsze o liczbie znaków). Następnie używam itertools.combinationsdo wybierania każdej kombinacji pustych miejsc, od 0 miejsc w górę. Przeglądam każdą kombinację Di wypisuje ona długość pierwszej, która działa, zgłaszając wyjątek, aby wyjść z programu. Jeśli nie znaleziono odpowiedzi, nic nie jest drukowane.

Zauważ, że obecnie program nie działa, jeśli nie są potrzebne ściany. Zajmą się tym +3 znaki; nie jestem pewien, czy to konieczne.

Zauważ też, że jest to O(2^n)algorytm, w którym njest liczba pustych miejsc. Tak więc, dla całkowicie pustej planszy 15x15 z jednym obozem pośrodku, zajmie to 2^(15*15-1)= 2.6959947e+67iteracje, co naprawdę potrwa bardzo długo!

Groovy: 841 805 754

i=new File("city.txt").getText()
x=i[2] as int
y=i[0] as int
m=i[4..i.length()-1].replaceAll('\n','').toList()
print r(m,0)
def r(m,n){if(f(m))return n;c=2e9;g(m).each{p=r(it,n+1);if(p<c)c=p;};return c;}
def f(m){u=[];u.addAll(m);for(i in 0..(x*y)){for(l in 0..m.size()-1){n(l,u);s(l,u);e(l,u);w(l,u);}};m.count('o')==u.count('o')}
def n(i,m){q=i-x;if((((q>=0)&(m[q]=='!'))|(q<0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def s(i,m){q=i+x;if((((q>=0)&(m[q]=='!'))|(q<0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def e(i,m){q=i+1;if((((q%x!=0)&(m[q]=='!'))|(q%x==0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def w(i,m){q=i-1;if((((i%x!=0)&(m[q]=='!'))|(i%x==0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def g(m){v=[];m.eachWithIndex{t,i->if(t=='.'){n=[];n.addAll(m);n[i]='W';v<<n}};return v}

Nie golfowany:

def i = new File("city.txt").getText()
x=i[2].toInteger()
y=i[0].toInteger()
def m=i[4..i.length()-1].replaceAll('\n','').toList()
println r(m, 0)

def r(m, n){
    if(f(m)) return n
    def c = Integer.MAX_VALUE

    getAllMoves(m).each{ it -> 
        def r = r(it, n+1)
        if(r < c) c = r
    }
    return c;
}

def f(m){
    def t = []
    t.addAll(m)
    for(i in 0..(x*y)){
        for(l in 0..m.size()-1){
            n(l,t);s(l,t);e(l,t);w(l,t);
        }
    }
    m.count('o')==t.count('o')
}

def n(i,m){
    def t = i-x;
    if( ( ( (t >= 0) && (m[t]=='!') ) || (t < 0)) && m[i]!='x' && m[i]!='W'){
        m[i]='!'
    }
}

def s(i,m){
    def t = i+x;
    if( ( ( (t >= 0) && (m[t]=='!') ) || (t < 0)) && m[i]!='x' && m[i]!='W'){
        m[i]='!'
    }
}

def e(i,m){
    def t = i+1;
    if( ( ( (t%x!=0) && (m[t]=='!') ) || (t%x==0)) && m[i]!='x' && m[i]!='W'){
        m[i]='!'
    } 
}

def w(i,m){
    def t = i-1;
    if( ( ( (i%x!=0) && (m[t]=='!') ) || (i%x==0)) && m[i]!='x' && m[i]!='W'){
        m[i]='!'
    }
}

def getAllMoves(m){
    def moves = []
    m.eachWithIndex { t, i ->
        if(t=='.'){
            def newList = []
            newList.addAll(m)
            newList[i]='W'
            moves << newList
        }
    }
    return moves
}

Jeszcze więcej golfa ...

Zwraca 2E9, jeśli nie ma rozwiązania.

Dyalog APL , 91 bajtów

⊃∊{1∊a[⍸×{(×d)∧s 3∨/3∨⌿⍵}⍣≡4=d←0@⍵⊢a]:⍬⋄≢⍵}¨c[⍋≢¨c←(,⍳2⊣¨b)/¨⊂b←⍸2=a←(s←(4,4,⍨⍉)⍣2)'xo.'⍳⎕]

zakłada ⎕IO=0, używa funkcji z wersji 16.0 ( @i ⍸), czas działania jest wykładniczy w liczbie .-s

⎕ jest analizowane wejście, musi być macierzą znaków

'xo.'⍳ zamień na x0, na o1, na .2, a wszystkie inne na 3

s←(4,4,⍨⍉)⍣2 funkcja otaczająca macierz 4s

a← przypisz macierz numeryczną otoczoną 4s do zmiennej a

b←⍸2= bto lista par współrzędnych, w których znajdują się 2s (tj. .-s)

(,⍳2⊣¨b)/¨⊂b generuj wszystkie kombinacje elementów b

c[⍋≢¨c←...] posortuj je według rozmiaru

{... :⍬⋄≢⍵}¨ dla każdej kombinacji sprawdź coś i zwróć jego długość lub pustą listę

⊃∊ pierwszy niepusty wynik

d←0@⍵⊢a djest az niektórymi elementami zastąpionymi przez 0

4= stworzyć macierz boolowską - gdzie są 4? tj. granicę, którą dodaliśmy

{...}⍣≡ stosuj tę funkcję, {}aż wynik się ustabilizuje

3∨/3∨⌿⍵ „boolean” lub „każdy element wraz z sąsiadami”

s wynik będzie mniejszy, więc ponownie stwórzmy granicę

(×d)∧ zastosuj niezerowe elementy d(nie-ścian) jako maskę logiczną

a[⍸× ...] co aodpowiada 1 w naszej macierzy boolowskiej?

1∊ czy są jakieś 1, czyli oobozowiska?