Введение

Знающие код гольфисты подготовили нас к потопу конца света . Районы, подверженные риску, были эвакуированы, и население переместилось на возвышенность.

Мы недооценили поток (или, возможно, была ошибка в коде @ user12345). Некоторые высокогорные районы стремительно приближаются к уровню моря. Стены должны быть возведены, чтобы обеспечить выживание ныне густонаселенных лагерей. К сожалению, правительство имеет ограниченный запас стен.

проблема

Наш сценарий конца света описывается двумя числами в одной строке, nи m. После этой строки идут nстроки со mзначениями в строке, разделенные только одним пробелом. Каждое значение будет одним из четырех символов.

• xНепроходимое. Вода не может течь здесь. Стены не могут быть возведены здесь.
• -Нестабильный. Вода может течь через это здесь. Стены не могут быть возведены здесь.
• .Стабильная. Вода может течь здесь. Стены могут быть возведены здесь.
• oЛагерь. Вода может течь здесь. Если это произойдет, все умрут. Стены не могут быть построены здесь.

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

Пример ввода

 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

Пример вывода

3

Предположения

• Вода течет только ортогонально
• Лагеря существуют только как один ортогонально непрерывный блок на сценарий
• Решение всегда будет существовать (хотя для этого может потребоваться большое количество стен)
• Лагеря не могут быть расположены на краю, так как сценарий не будет иметь решения
• 2 n<<16
• 2 m<<16
• Входные данные могут быть предоставлены из stdin, прочитаны из «city.txt» или приняты как один аргумент

Самый короткий код выигрывает!

Mathematica, 257 253 символов

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}]

Ввод читается из "city.txt".

Объяснение:

Mathematica имеет много функций для работы с графами.

Сначала я читаю данные из "city.txt".

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

Затем я строю сеточный граф с 'm' * 'n' vertices ( GridGraph@d[[1,{2,1}]]) и добавляю к нему «вершину на бесконечности», которая связана с каждой вершиной на «ребрах» графа. Эта вершина - то, откуда течет вода.

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

И o, xи sобозначают позиции «о», «х» и «.» соответственно.

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

Тогда для любого подмножества wиз s(подмножеств сортируются по длине), я удалить вершины в xи wиз g( VertexDelete[g,x⋃w]), а также найти длину кратчайшего пути от вершины «на бесконечности» до лагеря o. Если длина бесконечна, то лагерь будет в безопасности. Таким образом, длина первого такова w- это минимальное количество стен, необходимое для защиты лагеря.

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

С 827 799 522

Golfed:

#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);}

Входные данные задаются с высотой и в качестве аргументов командной строки, а затем сетка читается как одна строка в stdin следующим образом: ./a.out 6 7 < inputгде ввод находится в этой форме (слева направо, сверху вниз):

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

"Удобочитаемый":

#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");
    }   
}

Это далеко не так быстро, как решение @Claudiu, но оно работает невероятно быстро. Вместо заливки с краев он находит лагерь и работает наружу от жетонов «о».

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

Образцы размещения стен:

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 символов (+4 для вызова)

Мне было очень весело играть в гольф. Это на 82 байта больше, если вы попытаетесь сжать его! Теперь это мера компактности и отсутствия повторений.

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))

Уровни отступа - пробел, таб.

Использование :

Читает из 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

Вызовите следующим образом:

$ python floodfill_golf.py 2>X
3

Это 2>Xскрыть stderr, так как программа закрывается, вызывая исключение. Если это считается несправедливым, не стесняйтесь добавлять 4 символа для вызова.

Пояснение :

Простая грубая сила. Cвыполняет заливку и возвращает истину, если она попадает в лагерь. Никаких дополнительных отступов, так как для правильной настройки заполнения потребовалось слишком много места. Dс учетом набора стен, которые необходимо заполнить, звонки Cиз каждой точки на краю, так что они Cучитывают эти стены, и выводит длину и выходит, если ни одна из них не достигла лагеря. Список стен также используется для отслеживания заливки, поэтому копирование доски не требуется! Trickily, Cтакже добавляет любые пустые места , которые он находит в список S, так что функция Dбудет также использоваться для первой конструкции списка пустых мест. По этой причине я использую sumвместо того any, чтобы обеспечить все. s собраны при первом прогоне.

Я вызываю Dодин раз, затем копирую список пустых мест, Zтак как они Sбудут добавляться (неэффективно, но дешевле по количеству символов). Затем я использую, itertools.combinationsчтобы выбрать каждое комбо пустых мест, от 0 мест вверх. Я запускаю каждую комбинацию, Dи она печатает длину первой, которая работает, вызывая исключение для выхода из программы. Если ответ не найден, ничего не печатается.

Обратите внимание, что в настоящее время программа не работает, если не нужны никакие стены. Было бы +3 символа, чтобы заботиться об этом случае; не уверен, если это необходимо.

Также обратите внимание, что это O(2^n)алгоритм, где nколичество пустых мест. Таким образом, для полностью пустой доски размером 15x15 с одним лагерем посередине потребуется 2^(15*15-1)= 2.6959947e+67итераций для завершения, что будет очень долго!

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}

Ungolfed:

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
}

Гораздо больше игры в гольф ...

Возвращает 2E9, если нет решения.

Дьялог АПЛ , 91 байт

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

предполагает ⎕IO=0, использует функции v16.0 ( @и ⍸), время выполнения экспоненциально по числу .-s

⎕ оценивается ввод, должна быть матрица символов

'xo.'⍳ заменить xна 0, oна 1, .на 2, а все остальные на 3

s←(4,4,⍨⍉)⍣2 функция, которая окружает матрицу с 4s

a← назначить числовую матрицу, заключенную в 4 с переменной a

b←⍸2= bсписок пар координат, где 2s (то есть .-s)

(,⍳2⊣¨b)/¨⊂b генерировать все комбинации элементов b

c[⍋≢¨c←...] сортировать их по размеру

{... :⍬⋄≢⍵}¨ для каждой комбинации проверьте что-нибудь и верните либо его длину, либо пустой список

⊃∊ первый непустой результат

d←0@⍵⊢a d является a с некоторыми элементами заменены 0

4= создать булеву матрицу - где 4s? то есть границы мы добавили

{...}⍣≡ продолжайте применять функцию, {}пока результат не стабилизируется

3∨/3∨⌿⍵ «логический или» каждый элемент со своими соседями

s результат будет меньше, поэтому давайте воссоздадим границу

(×d)∧ применять ненулевые элементы d(не стены) в качестве логической маски

a[⍸× ...] что aсоответствует 1 в нашей логической матрице?

1∊ Есть ли 1s, то есть oлагеря?