LINUX.ORG.RU
решено Форум — Development  

Задача про лабиринт


0

1

Всем доброго времени суток. есть лабиринт «#» - стенка, "." коридор. Если заблудившийся приложит правую руку к стенке и будет идти до конца - он обязательно найдет выход. Нужно написать рекурсивную функцию, которая приведет заблудившегося к выходу. Я пробовал писать, но мой путник иногда возвращается к первоначальной точке, и у меня никак не получалось привязать его к правой стенке. Вот лабиринт. «Х» - путник. 


# # # # # # # # # # # #
# . . . # . . . . . . #
X . # . # . # # # # . #
# # # . # . . . . # . #
# . . . . # # # . # . .
# # # # . # . # . # . #
# . . # . # . # . # . #
# # . # . # . # . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #

← JavaScript научился исполнять Java-байткод
[epoll] Edge Triggered (ET) vs. Level Triggered (LT) →
 ← 1 2

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

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

# # # # # # # # # # # #
# . . . # . . . . . . #
X . # . # . # # # # . #
# # # . # . . . . # . #
# . . . . * * * . # . .
# # # # . * . * . # . #
# . . # . * . * . # . #
# # . # . * . * . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #
В общем, надо модифицировать алгоритм: если вернулся в исходную точку, переходить к другой стене (но и проверять, чтобы не было «мотыляния» между несколькими одними и теми же стенками).

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Кстати, если между левой верхней звездочкой и соседней с ней стенкой нет прохода, алгоритм должен работать.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

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

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

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

Хм. Прошелся и не заблудился. Сам попробуй :)

power ★
()
Ответ на: комментарий от power

Это я дурак, решил, что лабиринт вот такой: 

# # # # # # # # # # # #
# . . . # . . . . . . #
X . # . # . # # # # . #
# # # . . . . . . # . #
# . . . . * * * . # . .
# # # # . * . * . # . #
# . . # . * . * . # . #
# # . # . * . * . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #

Eddy_Em ☆☆☆☆☆
()

Так а в чем вопрос? Есть конкретно непонятный момент, или ты просто хочешь чтоб ЛОР все сделал за тебя?

morse ★★★★★
()

Можно проще, раз уж согласен на рекурсивную функцию. Вычисляем, куда можно пойти из текущей клетки, кроме как назад. Вызываем функцию поиска для первого, если ответ найден - завершить. Также для всех остальных вариантов. Если ничего не найдено, то задача решения не имеет.

note173 ★★★★★
()

Что тут писать? Алгоритм в функциональном стиле: 

Функция(лабиринт, положение путника) =
Если вне лабиринта -- победа;
Иначе: если можешь повернуть направо, то Функция(лабиринт, положение путника + поворот направо);
Иначе: если можешь идти прямо -- Функция(лабиринт, положение путника + шаг прямо);
Иначе: Функция(лабиринт, положение путника + поворот на 180)

kermzyxer ★
()

> но мой путник иногда возвращается к первоначальной точке
Ох, лол! Кажется, я понял вопрос. Точка, на которой стоит путник вначале — тоже выход из лабиринта, но не тот, который нам нужен: поэтому ее надо приравнять к стене.

kermzyxer ★
()
Ответ на: комментарий от yyk

> заблудившийся приложит правую руку к стенке и будет идти до конца

kermzyxer ★
()
Ответ на: комментарий от Eddy_Em

>> Если заблудившийся приложит правую руку к стенке и будет идти до конца - он обязательно найдет выход.

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

Если вход и выход расположены во внешних стенах лабиринта, то не будет никогда

anonymous
()
Ответ на: комментарий от deterok

Ну я алгоритм поиска пути имел ввиду. Он всегда находит путь, если таковой имеется.

deterok ★★★★★
()
Ответ на: комментарий от Eddy_Em

Алгоритм Тесея работает в случае существования единственного маршрута к выходу, такой случай имелся в виду?

# # # # # # # # # # # #
# . . . # . . . . . . #
# . # . # . # # # # . #
# # # . . . . . . # . #
# . . . . * * * . # . .
# # # # . * X * . # . #
# . . # . * . * . # . #
# # . # . * . * . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #

backbone ★★★★★
()
Ответ на: комментарий от NightmareZz

Набросал решение. Проходит «на ура»: 

using System;
using System.Collections.Generic;

namespace Maze
{
    class Program
    {
        private struct Point
        {
            public Point(int x, int y)
            {
                X = x;
                Y = y;
            }

            public readonly int X, Y;

            public static bool operator ==(Point pt0, Point pt1)
            {
                return pt0.X == pt1.X && pt0.Y == pt1.Y;
            }

            public static bool operator !=(Point pt0, Point pt1)
            {
                return !(pt0 == pt1);
            }
        }

        private static string[] CloneMaze(string[] maze, Point curr)
        {
            var result = new string[maze.Length];

            for (int j = 0; j < maze.Length; ++j)
            {
                result[j] = j != curr.Y
                    ? maze[j]
                    : maze[j].Remove(curr.X, 1).Insert(curr.X, "X");
            }

            return result;
        }

        private static void PrintMaze(IEnumerable<string> maze)
        {
            foreach (string s in maze)
                Console.WriteLine(s);
            Console.WriteLine();
        }

        private static void Go(string[] maze, Point curr, Point exit)
        {
            if (curr == exit)
            {
                Console.WriteLine("Result:");
                PrintMaze(CloneMaze(maze, curr));
            }
            else
            {
                if (curr.X > 0 && maze[curr.Y][curr.X - 1] == '.')
                    Go(CloneMaze(maze, curr), new Point(curr.X - 1, curr.Y), exit);

                if (curr.X < maze[0].Length - 1 && maze[curr.Y][curr.X + 1] == '.')
                    Go(CloneMaze(maze, curr), new Point(curr.X + 1, curr.Y), exit);

                if (curr.Y > 0 && maze[curr.Y - 1][curr.X] == '.')
                    Go(CloneMaze(maze, curr), new Point(curr.X, curr.Y - 1), exit);

                if (curr.Y < maze.Length - 1 && maze[curr.Y + 1][curr.X] == '.')
                    Go(CloneMaze(maze, curr), new Point(curr.X, curr.Y + 1), exit);
            }
        }

        static void Main()
        {
            var maze = new[]
            {
                "############",
                "#...#......#",
                "X.#.#.####.#",
                "###.#....#.#",
                "#....###.#..",
                "####.#.#.#.#",
                "#..#.#.#.#.#",
                "##.#.#.#.#.#",
                "#........#.#",
                "######.###.#",
                "#......#...#",
                "############"
            };

            int width = maze[0].Length;
            int height = maze.Length;

            Point? start = null;
            Point? exit = null;

            for (int j = 0; j < height && !(start.HasValue && exit.HasValue); ++j)
                for (int i = 0; i < width; ++i)
                    if (maze[j][i] == 'X')
                        start = new Point(i, j);
                    else
                        if ((i == 0 || i == width - 1 || j == 0 || j == height - 1) &&
                            maze[j][i] == '.')
                        {
                            exit = new Point(i, j);
                        }

            Console.WriteLine("Source:");
            PrintMaze(maze);

            if (start.HasValue && exit.HasValue)
                Go(maze, start.Value, exit.Value);
            Console.ReadKey();
        }
    }
}
Вывод: 
Source:
############
#...#......#
X.#.#.####.#
###.#....#.#
#....###.#..
####.#.#.#.#
#..#.#.#.#.#
##.#.#.#.#.#
#........#.#
######.###.#
#......#...#
############

Result:
############
#XXX#XXXXXX#
XX#X#X####X#
###X#XXXX#X#
#..XX###X#XX
####X#.#X#.#
#..#X#.#X#.#
##.#X#.#X#.#
#...XXXXX#.#
######.###.#
#......#...#
############

NightmareZz
()
Ответ на: комментарий от NightmareZz

Спасибо, но тут просто в задании указано использовать метод привязки к правой стенке, и без использования ООП. А ваш метод я разберу) просто я с ООП еще на «Вы».

JuST_KoReaN
() автор топика
Ответ на: комментарий от anonymous

у него там «ООП» понту дешевого ради

Я не понял, к чему ты придираешься? Тебе не нравится структура Point? Или nullable-типы? Или то, что я перегрузил оператор == вместо написания метода isPointsEqual?

У тебя походу ООП-баттхёрт. Я же использую инструменты, не заморачиваясь на такие нюансы - кошерно тут юзать «ООП» или это будет «ради дешёвого понта».

И, да, кстати, ни наследования, ни полиморфизма я не наблюдаю. Зато наблюдаю твою попаболь.

NightmareZz
()
Ответ на: комментарий от Eddy_Em

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

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

Harald ★★★★★
()
Ответ на: комментарий от NightmareZz

Он тебе и говорит, что смысла использования ООП в данном конкретном случае не было.

Вот например псевдокод в функциональном виде был гораздо понятнее и лаконичнее.

aedeph ★
()
Ответ на: комментарий от aedeph

Он тебе и говорит, что смысла использования ООП в данном конкретном случае не было.

Вот например псевдокод в функциональном виде был гораздо понятнее и лаконичнее.

Ну так напишите же кто-нибуть рабочий «правильный» код. Почему вы все только калом поливаете, но сами не готовы и мизинцем пошевельнуть? Тролли? Неосиляторы? Мифическое русское быдло? Что с вами?

NightmareZz
()
Ответ на: комментарий от NightmareZz

>Тролли? Неосиляторы? Мифическое русское быдло? Что с вами?

А с тобой что? Молодой-горячий-прыщи заели? Здесь не школа - учить не нанимались. Скажи спасибо, что хоть пинком указали верное направление. Но если ты не согласен - тогда доооооооо - дрочи дальше.

yyk ★★★★★
()
Ответ на: комментарий от aedeph

Ого, сколько эмоций. Ты верунчик в ООП что ли? Или просто не знаешь ничего кроме?

Ты покажешь, как нужно было написать «по-пацански» или то был пук в лужу?

NightmareZz
()
Ответ на: комментарий от cattail

A* или волновой алгоритм.

Тебя не смущает, я так понимаю, что в данной теме уже предлагали и A* и волновой алгоритм. Более того, волновой даже реализовали. Ты же элита, тебе не к лицу читать тему перед ответом, да?

Или обязательна рекурсия?

То есть ты бы реализовывал эти алгоритмы нерекурсивно, да, макака?

NightmareZz
()
Ответ на: комментарий от NightmareZz

А, не прочитал ваше первое сообщение. Однако ТСу же надо «правило правой руки».

buddhist ★★★★★
()
Ответ на: комментарий от cattail

>A* или волновой алгоритм. Или обязательна рекурсия?

Написано рекурсия

JuST_KoReaN
() автор топика
Ответ на: комментарий от NightmareZz

Задачу решил) Объявил 2 массива, route_x && route_y в зависимости от направления куда нам надо, они увеличивают или уменьшают координаты x и y соответственно. Сперва идет проверка стены справа, если стены нет, поворот направо, и изменяем направление (т. е. выбираем другие элементы массивов route_%) если стена есть, проверяем спереди, если нет, делаем шаг, если есть, поворот налево без изменений координат, а только с изменением направления (route_%). Ну и условия выхода конечно. 

#include <iostream>
#include <iomanip>
#include <ctime>
using namespace std;

const int mazeSize = 12;
int route_X[4] = {1, 0, -1, 0}; // 4 ways to move
int route_Y[4] = {0, 1, 0, -1};
int i = 0; // switcher
char maze[ mazeSize ][ mazeSize ] = {
    {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
  , {'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'}
  , {'.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#'}
  , {'#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#'}
  , {'#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.'}
  , {'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'}
  , {'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'}
  , {'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'}
  , {'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'}
  , {'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'}
  , {'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#'}
  , {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}}; // our maze

void wait (int); // wait for half a second

class Traverse
{
public:
  Traverse(int, int);
  void define_route(); // where we gonna move to
  bool checkWall(); // check existence of the right wall
  int checkForward(); // check any barriers in front of him
  void turnRight(); // turn to the right plus step
  void turnLeft(); // turn to the left only
  void step(); // check around
  void displayPos(); // display maze with my position
  
private:
  int beginX; // begining
  int beginY; // position
  int stepX; // increament
  int stepY; // increament
  int x; // my position
  int y; // my position
};

Traverse::Traverse(int x0, int y0)
{
  beginX = x0;
  beginY = y0;
  x = beginX;
  y = beginY;
  maze[y][x] = 'X';
}

void Traverse::define_route()
{
  if (beginX + 1 > mazeSize) i = 2;
  else if (beginX - 1 < 0) i = 0;
  else if (beginY + 1 > mazeSize) i = 3;
  else if (beginY - 1 < 0) i = 1;
  
  stepX = route_X[i];
  stepY = route_Y[i];
}

bool Traverse::checkWall()
{
  int n, m;
  if (i == 3)
    {
      n = route_Y[0];
      m = route_X[0];
    }
  else
    {
      n = route_Y[i+1];
      m = route_X[i+1];
    }
  if (maze[y + n][m + x] == '#')
    return true;
  else
    return false;
}

int Traverse::checkForward()
{
  if (maze[y + stepY][x + stepX] == '.')
    return 1;
  else
    {
      if (x + stepX == 12 || x + stepX == -1 || y + stepY == 12 || y + stepY == -1)
	return -1;
      else
	return 0;
    }
}

void Traverse::turnRight()
{
  if (i == 3) i = 0;
  else i++;

  stepX = route_X[i];
  stepY = route_Y[i];

  maze[y][x] = '.';
  x += stepX;
  y += stepY;
  maze[y][x] = 'X';
  displayPos();
  step();
  
}

void Traverse::turnLeft()
{
  if (i == 0) i = 3;
  else i--;

  stepX = route_X[i];
  stepY = route_Y[i];

}

void Traverse::step()
{
  if (checkWall())
    {
      switch (checkForward())
	{
	case -1:
	  cout << "We have found exit!!!" << endl;
	  break;
	case 0:
	  turnLeft();
	  step();
	  break;
	case 1:
	  maze[y][x] = '.';
	  x += stepX;
	  y += stepY;
	  maze[y][x] = 'X';
	  displayPos();
	  step();
	  break;
	}
    }
  else
    {
      turnRight();
    }

}

void Traverse::displayPos()
{
  for (int i = 0; i < mazeSize; i++)
    {
      for (int j = 0; j < mazeSize; j++)
	{
	  cout << setw(2) << maze[i][j];
	}
      cout << endl;
    }
  cout << endl;
  wait(1);
}

void wait ( int seconds )
{
  clock_t endwait;
  endwait = clock () + seconds * CLOCKS_PER_SEC/2 ;
  while (clock() < endwait) {}
}



int main()
{
  Traverse man(0, 2);
  man.define_route();
  man.step();

  return 0;
}

JuST_KoReaN
() автор топика
Ответ на: комментарий от cdslow

Я бы все таки это полноценным ООП не назвал. Хочу просто практиковаться потихонечку. Просто описал класс. Тем более по моему мнению очень емкий.

JuST_KoReaN
() автор топика
Ответ на: комментарий от cdslow

> без использования ООП > class Traverse Ничего странного не находите?

Я нахожу странным тот факт, что использование классов вы называете ООП. Я плачу кровавыми слезами, понимая, что живу на одной планете с такими «специалистами».

NightmareZz
()

Немного экзотики: 

\ -------------------------------------------------------------------  
char # constant wall
char . constant pol
char X constant man
char * constant star
char & constant corpse
\ -------------------------------------
: str,    here over char+ allot place ;
: maze,"  34 parse str, ;
\ #cccccccccccc
\ #cccccccccccc
\ #cccccccccccc
\ #cccccccccccc
0 value maze
0 value /maze
here to maze
maze," ############"
maze," #...#......#"
maze," X.#.#.####.#"
maze," ###.#....#.#"
maze," #....###.#.."
maze," ####.#.#.#.#"
maze," #..#.#.#.#.#"
maze," ##.#.#.#.#.#"
maze," #........#.#"
maze," ######.###.#"
maze," #......#...#"
maze," ############"
here to /maze
: maze#size  /maze maze - ;
: maze#cols  maze c@ ;
: maze#lins  maze#size maze#cols 1+ / ;
: XY2addr { X Y -- addr } 
  Y 1-  maze#cols 1+  *  X +  maze + ;
: addr2XY { addr -- X Y } 
  addr maze -  maze#cols 1+  /mod 1+ ;
\ -------------------------------------
0 value X 
0 value Y 
X value X0
Y value Y0
\ -------------------------------------
: findX ( -- )
  maze#lins 0 ?do 
    maze#cols 1+ I * maze + 1+ maze c@  s" X"  search 
    if drop addr2XY to Y to X else 2drop endif
  loop  X to X0  Y to Y0 ; 
: iswall? XY2addr c@ wall = ;
: ispol?  XY2addr c@ pol  = ;
: isman?  XY2addr c@ man  = ;
\ -------------------------------------
8 value direction
\ -------------------------------------
\   8
\ 4-|-6
\   2
: aheadXY ( -- aX aY )
  direction case
      8 of X    Y 1- endof
      6 of X 1+ Y    endof
      2 of X    Y 1+ endof
      4 of X 1- Y    endof
  endcase ;
: rightXY ( -- rX rY )
   direction case 
      8 of X 1+ Y    endof
      6 of X    Y 1+ endof
      2 of X 1- Y    endof
      4 of X    Y 1- endof
  endcase ;
: rturn ( -- )
  direction case 
    8 of 6 endof
    6 of 2 endof
    2 of 4 endof
    4 of 8 endof
    8
  endcase  to direction ;
: lturn ( -- )
  direction case 
    6 of 8 endof
    8 of 4 endof
    4 of 2 endof
    2 of 6 endof
    8
  endcase  to direction ;
\ -------------------------------------
0    value    #step
1000 value max#step
: #step+1 #step 1+ to #step ;
\ -------------------------------------
: printSTATE 
  cr
  ." step: " #step . cr
  maze#lins 0 ?do 
    I 1+ 3 .r ." : " 
    maze#cols 1+ I * maze + 1+ maze c@ type cr 
  loop  cr ; 
\ -------------------------------------
: freedom?     X maze#cols =   Y maze#lins =   or ;
: back2start?  X X0 =   Y Y0 =  and  #step 1 > and ;
: starvation?  #step max#step > ;
: *markcorpse*  corpse X Y XY2addr c! ;
: *markstar*    star   X Y XY2addr c! ;
: *markman*     man    X Y XY2addr c! ;
\ -------------------------------------
: go recursive 
  #step+1 
  starvation? if *markcorpse* ." Died of starvation." exit endif
  back2start? if ." Back to start point." exit endif
  printSTATE 
\ ----------
  freedom? if 
    cr ." Exit. FREEDOM! ROCK'N'ROLL!" cr
  else 
    rightXY iswall?  
    if
      aheadXY iswall?  
      if
        *markstar*  lturn  *markman*  go
      else
        *markstar*  aheadXY to Y to X  *markman*  go
      endif
    else
      *markstar*  rturn  aheadXY to Y to X  *markman*  go
    endif
  endif ;
\ -------------------------------------
: main
  printSTATE
  findX
  go
  printSTATE ;
\ -------------------------------------------------------------------
main
bye
Сохранить maze.fs
Запускать: 
$ gforth maze.fs
$ gforth maze.fs | less

Neksys ★★★
()
Ответ на: комментарий от Neksys 

step: 0 
  1: ########################################################################
  2: #...#......#....#......##...#......##...#......#....#......#....#......#
  3: X.#.#.####.#..#.#.####.#..#.#.####....#.#.####.#..#.#.####.#..#.#.####.#
  4: ###......#.####......#.####......#.####......#.####......#.####......#.#
  5: #....###.#.......###.#..#....###.#..#....###.#..#....###.#..#....###.#..
  6: ####.#.#.#.#####.#.#.#.#####.#.#.#.#####.#.#.#.#####.#.#.#.#####.#.#.#.#
  7: #..#.#.#.#..#..#.#.#.#..#..#.#.#.#.....#.#.#.#.#...#.#.#.#..#..#.#.#.#.#
  8: ##.#.#.#.#.###.#.#.#.#.###.#.#.#.#.###.#.#.#.#.###.#.#.#.#..##.#.#.#.#.#
  9: #........#.#.........#...........#.#.........#...........#...........#.#
 10: ######.###.#######.###.#######.###.#######.###.#######.###..######.###.#
 11: #..................#....#......#...#...................#....#..........#
 12: ########################################################################


Exit. FREEDOM! ROCK'N'ROLL!

step: 290 
  1: ########################################################################
  2: #***#......#....#******##...#******##...#......#....#******#....#......#
  3: **#*#.####.#..#.#*####*#..#.#*####*...#.#.####.#..#.#*####*#..#.#.####.#
  4: ###*.....#.####..****#*####..****#*####......#.####..****#*####......#.#
  5: #****###.#.......###*#*.#....###*#*.#....###.#..#....###*#*.#....###.#*X
  6: ####*#.#.#.#####.#.#*#*#####.#.#*#*#####.#.#.#.#####.#.#*#*#####.#.#.#*#
  7: #**#*#.#.#..#..#.#.#*#*.#..#.#.#*#*****#.#.#.#.#...#.#.#*#*.#..#.#.#.#*#
  8: ##*#*#.#.#.###.#.#.#*#*###.#.#.#*#*###*#.#.#.#.###.#.#.#*#*.##.#.#.#.#*#
  9: #******..#.#......***#***********#*#*******..#........***#*********..#*#
 10: ######*###.#######*###*#######*###*#######*###.#######*###**######*###*#
 11: #******************#****#******#***#*******************#****#**********#
 12: ########################################################################
Neksys ★★★
()
Ответ на: комментарий от Neksys

э... чтоб получить предыдущую картинку, нужно поменять кусок описания лабиринта на этот :) 

here to maze
maze," ########################################################################"
maze," #...#......#....#......##...#......##...#......#....#......#....#......#"
maze," X.#.#.####.#..#.#.####.#..#.#.####....#.#.####.#..#.#.####.#..#.#.####.#"
maze," ###......#.####......#.####......#.####......#.####......#.####......#.#"
maze," #....###.#.......###.#..#....###.#..#....###.#..#....###.#..#....###.#.."
maze," ####.#.#.#.#####.#.#.#.#####.#.#.#.#####.#.#.#.#####.#.#.#.#####.#.#.#.#"
maze," #..#.#.#.#..#..#.#.#.#..#..#.#.#.#.....#.#.#.#.#...#.#.#.#..#..#.#.#.#.#"
maze," ##.#.#.#.#.###.#.#.#.#.###.#.#.#.#.###.#.#.#.#.###.#.#.#.#..##.#.#.#.#.#"
maze," #........#.#.........#...........#.#.........#...........#...........#.#"
maze," ######.###.#######.###.#######.###.#######.###.#######.###..######.###.#"
maze," #..................#....#......#...#...................#....#..........#"
maze," ########################################################################"
here to /maze
hint: можно закоментировать вызов printSTATE в слове go и получить только первый и последний снимки.

Neksys ★★★
()

[ололо][нетмозга][нечегоделать][быдлокод] 44 строчки!

package labirinth
import java.io._
import java.util.Scanner
import scala.annotation.tailrec
object Main {
  class TextFile(stream:InputStream) extends Iterable[String]{
    val scanner = new Scanner(stream)
    def iterator = new Iterator[String]{
      def hasNext = scanner.hasNextLine
      def next = scanner.nextLine
    }
  }
  case class Point(i:Int, j:Int){
    def +(that:Point) = Point(i+that.i,j+that.j)
    override def toString = "["+i+","+j+"]"
    def rotateClockWise = Point(j,-i)
    def rotateCouterWise = Point(-j,i)
  }
  class Labirinth(i:InputStream){
    val grid = new TextFile(i).map(x=>x.filter(_!=' ').toArray).toArray
    val max = Point(grid.size-1,grid(0).size-1)
    val start = grid.zipWithIndex.foldLeft(Point(-1,-1)){(acc,line)=>
      if(line._1.contains('X')) Point(line._2, line._1.indexOf('X')) else acc
    }
    def directionHelper(value:Int, maxValue:Int, fromZero:Int):Int = value match{
      case 0 => fromZero
      case x if x==maxValue => -fromZero
      case _ => 0
    }
    val startDirection = Point(directionHelper(start.i,max.i,-1),directionHelper(start.j,max.j,1))
    def canGo(position:Point) = grid(position.i)(position.j)=='.'
    @tailrec
    private def go(position:Point, direction:Point,way:List[Point]):List[Point] = position match {
      case q@(Point(0,_) | Point(_,0) | Point(max.i,_) | Point(_,max.j)) if q!=start => way
      case _ => {
          var newDirection = direction.rotateClockWise
          while (!canGo(position+newDirection)) newDirection = newDirection.rotateCouterWise
          go(position+newDirection, newDirection, position::way)
      }
    }
    def run = println(go(start, startDirection, List()).reverse)
  } 
  def main(args: Array[String])= new Labirinth(new FileInputStream("input.txt")).run
}
vertexua ★★★★★
()
Ответ на: [ололо][нетмозга][нечегоделать][быдлокод] 44 строчки! от vertexua

Это scala? 

$ scalac ./maze.scala 
./maze.scala:20 error: illegal start of simple expression
    val grid = new TextFile(i).map(x=>x.filter(_!=' ').toArray).toArray
                                               ^
./maze.scala:41 error: ')' expected but '}' found.
    def run = println(go(start, startDirection, List()).reverse)
                                                                ^
two errors found
$ scalac -version
scalac unknown version -- (c) 2002-2006 LAMP/EPFL

Neksys ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
 ← 1 2
← JavaScript научился исполнять Java-байткод
Development
[epoll] Edge Triggered (ET) vs. Level Triggered (LT) →