Zburz ściany w labiryncie

Zasady:

W tej grze zaczynasz na szczycie prostokątnej siatki o wymiarach N x M złożonej ze ścian i otwartych przestrzeni. Dane wejściowe to N wierszy M znaków, gdzie znak .określa otwartą przestrzeń, a xścianę. Twój program powinien wypisać najmniejszą liczbę K, tak aby istniała ścieżka od lewego górnego rogu do prawego dolnego rogu (bez przekątnych), która przecina ściany K.

Na przykład, biorąc pod uwagę dane wejściowe:

..x..
..x..
xxxxx
..x..
..x..

twój program powinien wypisać 2.

Inne przykłady:

wyjście 4:

xxxxx
x.x.x
x.x.x
x..xx

wyjście 0:

.xxxxxxxx
.x...x...
.x.x.x.x.
.x.x...x.
...xxxxx.

wyjście 6:

xx
xx
xx
xx
xx

Dodatkowe ciekawostki:

Jeśli to ułatwi ci życie, możesz określić N i M jako parametry wiersza poleceń.

Dodatkowy kredyt, jeśli Twój program może wydrukować ścieżkę w takiej lub innej formie.

Rubinowy 1,9 (235) (225) (222) (214)

Nie wiem, czy jest to krótszy program niż program oparty na Dijkstrze, ale pomyślałem, że spróbuję innego podejścia. Używa wyrażenia regularnego w pętli, aby zaznaczyć każdą przestrzeń minimalną liczbą ścian wymaganych do jej osiągnięcia.

w=".{#{/\s/=~s=$<.read}}?"
j="([.x])"
s[0]=v=s[0]<?x??0:?1
(d=v[-1];n=v.succ![-1]
0while(s.sub!(/#{j}(#{w+d})/m){($1<?x?d: n)+$2}||s.sub!(/(#{d+w})#{j}/m){$1+($2<?x?d: n)}))while/#{j}/=~q=s[-2]
p v.to_i-(q==n ?0:1)

Dane wejściowe są określone jako plik w wierszu poleceń, tj

> ruby1.9.1 golf.rb maze.txt

Nie golfowany:

# read in the file
maze = $<.read

# find the first newline (the width of the maze)
width = /\s/ =~ maze

# construct part of the regex (the part between the current cell and the target cell)
spaces = ".{#{width}}?"

# construct another part of the regex (the target cell)
target = "([.x])"

# set the value of the first cell, and store that in the current wall count
maze[0] = walls = (maze[0] == "x" ? "1" : "0")

# loop until the goal cell is not "." or "x"
while /#{target}/ =~ (goal = s[-2])

  # store the current wall count digit and the next wall count digit, while incrementing the wall count
  current = walls[-1]; next = walls.succ![-1]

  # loop to set all the reachable cells for the current wall count
  begin

    # first regex handles all cells above or to the left of cells with the current wall count
    result = s.sub!(/#{target}(#{spaces + current})/m) {
      ($1 == 'x' ? next : current) + $2
    }

    # second regex handles all cells below or to the right of cells with the current wall count
    result = result || s.sub!(/(#{current + spaces})#{target}/m) {
      $1 + ($2 == 'x' ? next : current)
    }
  end while result != nil
end

# we reached the goal, so output the wall count if the goal was a wall, or subtract 1 if it wasn't
puts walls.to_i - (goal == next ? 0 : 1)

Perl 5.10 (164)

undef$/;$_=<>;/\n/;$s="(.{$-[0]})?";substr$_,0,1,($n=/^x/||0);
until(/\d$/){1while s/([.x])($s$n)/$n+($1eq x).$2/se
+s/$n$s\K[.x]/$n+($&eq x)/se;$n++}
/.$/;print"$&\n"

Bardzo podobnie jak rozwiązanie migimaru, tylko z tym dodatkowym dotykiem Perla. 5.10 jest potrzebne dla \Kw s///.

Python 406 378 360 348 418 znaków

import sys
d={}
n=0
for l in open(sys.argv[1]):
 i=0
 for c in l.strip():m=n,i;d[m]=c;i+=1
 n+=1
v=d[0,0]=int(d[0,0]=='x')
X=lambda *x:type(d.get(x,'.'))!=str and x
N=lambda x,y:X(x+1,y)or X(x-1,y)or X(x,y+1)or X(x,y-1)
def T(f):s=[(x,(v,N(*x))) for x in d if d[x]==f and N(*x)];d.update(s);return s
while 1:
 while T('.'):pass
 v+=1
 if not T('x'):break
P=[m]
s,p=d[m]
while p!=(0,0):P.insert(0,p);x,p=d[p]
print s, P

Uproszczona Dijkstra, ponieważ ruchy z ciężarem są na xpolu. Odbywa się to w „falach”, pierwszej pętli, w której znajdują się .pola dotykające przodu i ustawia się je na tej samej wadze, niż raz znajdowały xpola dotykające przodu i ustawiały je na +1wadze. Powtarzaj, dopóki nie będzie już niewidzianych pól.

Na koniec znamy wagę dla każdego pola.

Dane wejściowe są określone jako plik w wierszu poleceń:

python m.py m1.txt

Aktualizacja: drukuje ścieżkę.

Wersja C ++ (610 607 606 584)

#include<queue>
#include<set>
#include<string>
#include<iostream>
#include<memory>
#define S second
#define X s.S.first
#define Y s.S.S
#define A(x,y) f.push(make_pair(s.first-c,make_pair(X+x,Y+y)));
#define T typedef pair<int
using namespace std;T,int>P;T,P>Q;string l;vector<string>b;priority_queue<Q>f;set<P>g;Q s;int m,n,c=0;int main(){cin>>m>>n;getline(cin,l);while(getline(cin,l))b.push_back(l);A(0,0)while(!f.empty()){s=f.top();f.pop();if(X>=0&&X<=m&&Y>=0&&Y<=n&&g.find(s.S)==g.end()){g.insert(s.S);c=b[X][Y]=='x';if(X==m&&Y==n)cout<<-(s.first-c);A(1,0)A(-1,0)A(0,1)A(0,-1)}}}

Implementuje algorytm Dijkstry.

Bez golfa:

#include<queue>
#include<set>
#include<string>
#include<iostream>
#include<memory>

using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>Q;

int main()
{
    int             m,n;
    string          line;
    vector<string>  board;

    cin >> m >> n;getline(cin,l);
    while(getline(cin,line))
    {
        board.push_back(line);
    }

    priority_queue<Q>   frontList;
    set<P>              found;
    frontList.push(make_pair(0,make_pair(0,0)));
    while(!frontList.empty())
    {
        Q s=frontList.top();
        frontList.pop();
        if(   s.second.first>=0
           && s.second.first<=m
           && s.second.second>=0
           && s.second.second<=n
           && found.find(s.second)==found.end()
        )
        {
            found.insert(s.second);
            int c=board[s.second.first][s.second.second]=='x';
            if(  s.second.first==m
              && s.second.second==n
            )
            {   cout<<-(s.first-c);
            }
            frontList.push(make_pair(s.first-c,make_pair(s.second.first+1,s.second.second)));
            frontList.push(make_pair(s.first-c,make_pair(s.second.first-1,s.second.second)));
            frontList.push(make_pair(s.first-c,make_pair(s.second.first,s.second.second+1)));
            frontList.push(make_pair(s.first-c,make_pair(s.second.first,s.second.second-1)));
        }
    }
}