Codegolf — Снести Стены В Лабиринте

Правила:

В этой игре вы начинаете с вершины прямоугольной сетки размером N x M, состоящей из стен и открытых пространств. Входные данные — N строк из M символов, где a

 
 
 
 xx
xx
xx
xx
xx
 
 
 
 

specifies an open space and a 6 указывает стену. Ваша программа должна вывести наименьшее число K такое, чтобы существовал путь из верхнего левого угла в нижний правый угол (без диагоналей), пересекающий K стен.

Например, учитывая ввод:

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

ваша программа должна вывести 0 .

Другие примеры:

выход xxxxx x.x.x x.x.x x..xx :

4

выход 2 :

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

выход x :

.

Дополнительные вкусности:

Если это облегчит вам жизнь, вы можете указать N и M в качестве параметров командной строки.

Дополнительный балл, если ваша программа может распечатать путь в той или иной форме.

#код-гольф #лабиринт

Рубин 1,9 (235) (225) (222) (214)

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

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

}

}
}
 
 
 
 
 
 
 
 

Ввод указывается в виде файла в командной строке, т.е.

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

Не в гольфе:

python m.py m1.txt ||answer||

Перл 5.10 (164)

+1

Почти то же самое, что и решение Мигимару, только с добавлением Perl. 5.10 нужен для x in . .

Python 406 378 360 348 418 символов

x

Упрощенный Дейкстра, поскольку включены движения с весом. 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 field. It is done in "waves", first loop with finding s/// поля соприкасаются спереди и придают им тот же вес, чем однажды найти \K fields touching front and set them on 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" масса. Повторяйте, пока не останется непросмотренных полей.

В конце мы знаем вес для каждого поля.

Ввод указывается в виде файла в командной строке:

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

Обновлять: печатает путь.

Версия С++ (610 607 606 584)

> ruby1.9.1 golf.rb maze.txt

Реализует алгоритм Дейкстры.

Без игры в гольф:

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)