Классическая задача при игре в лабиринте состоит в поиске прохода через него от входа до выхода. Путь-решение рисуется на карте лабиринта. В большинстве случаев лабиринты генерятся компьютерами, которые пользуются алгоритмами вроде поиска в глубину. Интересно, что решать лабиринт можно при помощи того же самого алгоритма.
#### Читаем лабиринт
Лабиринт можно представлять в разных форматах. Мы будем использовать SVG, поскольку в этом случае легко будет нарисовать решение поверх него.
<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "
http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="112" height="96" version="1.1" xmlns="
http://www.w3.org/2000/svg">
<rect width="112" height="96" fill="white" stroke="none" />
<title>5 by 4 orthogonal maze</title>
<g fill="none" stroke="#000000" stroke-width="3" stroke-linecap="round" stroke-linejoin="round">
<line x1="16" y1="16" x2="32" y2="16" />
<line x1="48" y1="16" x2="80" y2="16" />
<line x1="16" y1="80" x2="96" y2="80" />
<line x1="16" y1="16" x2="16" y2="80" />
<line x1="96" y1="16" x2="96" y2="80" />
<line x1="64" y1="16" x2="64" y2="32" />
<line x1="32" y1="32" x2="32" y2="48" />
<line x1="32" y1="32" x2="48" y2="32" />
<line x1="64" y1="32" x2="64" y2="48" />
<line x1="64" y1="32" x2="80" y2="32" />
<line x1="32" y1="48" x2="48" y2="48" />
<line x1="48" y1="48" x2="48" y2="64" />
<line x1="48" y1="48" x2="64" y2="48" />
<line x1="80" y1="48" x2="80" y2="64" />
<line x1="16" y1="64" x2="32" y2="64" />
<line x1="48" y1="64" x2="64" y2="64" />
<line x1="80" y1="64" x2="80" y2="80" />
</g>
<g fill="black" stroke="none" stroke-width="1">
<text x="24" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">1</text>
<text x="40" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">2</text>
<text x="56" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">3</text>
<text x="72" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">4</text>
<text x="88" y="26" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">5</text>
<text x="24" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">6</text>
<text x="40" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">7</text>
<text x="56" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">8</text>
<text x="72" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">9</text>
<text x="88" y="42" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">10</text>
<text x="24" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">11</text>
<text x="40" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">12</text>
<text x="56" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">13</text>
<text x="72" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">14</text>
<text x="88" y="58" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">15</text>
<text x="24" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">16</text>
<text x="40" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">17</text>
<text x="56" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">18</text>
<text x="72" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">19</text>
<text x="88" y="74" text-anchor="middle" style="font-family:Arial Narrow; font-size: xx-small;">20</text>
</g>
</svg>
![][1] Файл мы будем обрабатывать двумя регулярками – одна для размера, а вторая – для поиска линий. [Читать дальше →][2]
[1]: //habrastorage.org/files/230/b16/b2f/230b16b2f426458099389b899dcfdcdb.png
[2]:
http://habrahabr.ru/post/257251/#habracut