자바-조금 더 똑똑하고 빠름

꽤 많은 코드가 있습니다. 나는 두 개의 Dijkstra 통과 (하나는 바위를 만났을 때 멈추고 다른 하나는 바위를 무시한다)를 기반으로하는 “이것이 보물을 얻는 방법은 얼마나 될까”의 순서로 푸시를 평가함으로써 더 빨리 노력하고 있습니다. 그것은 꽤 잘 작동하고 있으며 저자에게 귀찮은 페이스트 빈의 한 가지 예는이 구현으로 2 초 정도 해결됩니다. 다른 예제는 최대 30-40 초가 걸리지 만 너무 오래 걸리지 만 물건을 깨지 않고는 개선 할 수 없었습니다. 🙂

더 나은 구조를 얻기 위해 여러 파일로 물건을 나눕니다 (루비에서 Java로 전환 한 이유).

진입 지점:

import java.util.Date;
public class IndianaJones {
    public static void main(final String[] args) throws Exception {
        final Maze maze = new Maze(System.in);
        final Date startAt = new Date();
        final int solution = maze.solve();
        final Date endAt = new Date();
        System.out.printf("Found solution: %s in %d ms.",
                          solution < Integer.MAX_VALUE ? solution : "X",
                          endAt.getTime() - startAt.getTime());
    }
}

방향 도우미 열거 형 :

enum Direction {
    UP(-1, 0), DOWN(1, 0), LEFT(0, -1), RIGHT(0, 1);

    public final int drow;
    public final int dcol;

    private Direction(final int drow, final int dcol) {
        this.drow = drow;
        this.dcol = dcol;
    }

    public final Direction opposite() {
        switch (this) {
        case UP:
            return DOWN;
        case DOWN:
            return UP;
        case LEFT:
            return RIGHT;
        case RIGHT:
            return LEFT;
        }
        return null;
    }
}

“미로”의 위치를 ​​나타내는 추상 클래스 :

abstract class PointOfInterest {
    public final int row;
    public final int col;

    protected PointOfInterest(final int row, final int col) {
        this.row = row;
        this.col = col;
    }

    public final boolean isAt(final int row, final int col) {
        return this.row == row && this.col == col;
    }

    @Override
    public final String toString() {
        return getClass().getSimpleName() + "(" + row + ", " + col + ")";
    }

    @Override
    public final int hashCode() {
        return row ^ col;
    }

    @Override
    public final boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!(obj instanceof PointOfInterest))
            return false;
        if (!getClass().equals(obj.getClass()))
            return false;
        final PointOfInterest other = (PointOfInterest) obj;
        return row == other.row && col == other.col;
    }
}

그리고 마지막으로 미로 자체 :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.EnumSet;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class Maze {
    private static final char WALL = '1';
    private static final char INDY = '2';
    private static final char GOAL = '3';
    private static final char ROCK = '4';

    private final Maze parent;
    private final Set<Maze> visited;
    private final boolean[][] map;
    private final int[][] dijkstra;
    private int[][] dijkstraGhost;
    private String stringValue = null;

    private int shortestSolution = Integer.MAX_VALUE;

    private Goal goal = null;
    private Indy indy = null;
    private Set<Rock> rocks = new HashSet<>();

    private Maze(final Maze parent, final Rock rock, final Direction direction) {
        this.parent = parent;
        this.visited = parent.visited;
        map = parent.map;
        dijkstra = new int[map.length][map[rock.row].length];
        for (final int[] part : dijkstra)
            Arrays.fill(part, Integer.MAX_VALUE);
        goal = new Goal(parent.goal.row, parent.goal.col);
        indy = new Indy(rock.row, rock.col);
        for (final Rock r : parent.rocks)
            if (r == rock)
                rocks.add(new Rock(r.row + direction.drow, r.col + direction.dcol));
            else
                rocks.add(new Rock(r.row, r.col));
        updateDijkstra(goal.row, goal.col, 0, true);
    }

    public Maze(final InputStream is) {
        this.parent = null;
        this.visited = new HashSet<>();
        try (final BufferedReader br = new BufferedReader(new InputStreamReader(is))) {
            String line = br.readLine();
            final String[] sizeParts = line.split(" ");
            final int height = Integer.parseInt(sizeParts[0]);
            final int width = Integer.parseInt(sizeParts[1]);
            map = new boolean[height][width];
            dijkstra = new int[height][width];

            int row = 0;
            while ((line = br.readLine()) != null) {
                for (int col = 0; col < line.length(); col++) {
                    final char c = line.charAt(col);
                    map[row][col] = c == WALL;
                    dijkstra[row][col] = Integer.MAX_VALUE;
                    if (c == INDY) {
                        if (indy != null)
                            throw new IllegalStateException("Found a second indy!");
                        indy = new Indy(row, col);
                    } else if (c == GOAL) {
                        if (goal != null)
                            throw new IllegalStateException("Found a second treasure!");
                        goal = new Goal(row, col);
                    } else if (c == ROCK) {
                        rocks.add(new Rock(row, col));
                    }
                }
                row++;
            }

            updateDijkstra(goal.row, goal.col, 0, true);
        } catch (final IOException ioe) {
            throw new RuntimeException("Could not read maze from InputStream", ioe);
        }
    }

    public int getShortestSolution() {
        Maze ptr = this;
        while (ptr.parent != null)
            ptr = ptr.parent;
        return ptr.shortestSolution;
    }

    public void setShortestSolution(int shortestSolution) {
        Maze ptr = this;
        while (ptr.parent != null)
            ptr = ptr.parent;
        ptr.shortestSolution = Math.min(ptr.shortestSolution, shortestSolution);
    }

    private final boolean isRepeat(final Maze maze) {
        return this.visited.contains(maze);
    }

    private final void updateDijkstra(final int row, final int col, final int value, final boolean force) {
        if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
            return;
        if (map[row][col] || isRockPresent(row, col))
            return;
        if (dijkstra[row][col] <= value && !force)
            return;

        dijkstra[row][col] = value;
        updateDijkstra(row - 1, col, value + 1, false);
        updateDijkstra(row + 1, col, value + 1, false);
        updateDijkstra(row, col - 1, value + 1, false);
        updateDijkstra(row, col + 1, value + 1, false);
    }

    private final void updateDijkstraGhost(final int row, final int col, final int value, final boolean force) {
        if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
            return;
        if (map[row][col] || isRockPresent(row, col))
            return;
        if (dijkstraGhost[row][col] <= value && !force)
            return;

        dijkstraGhost[row][col] = value;
        updateDijkstraGhost(row - 1, col, value + 1, false);
        updateDijkstraGhost(row + 1, col, value + 1, false);
        updateDijkstraGhost(row, col - 1, value + 1, false);
        updateDijkstraGhost(row, col + 1, value + 1, false);
    }

    private final int dijkstraScore(final int row, final int col) {
        if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
            return Integer.MAX_VALUE;
        return dijkstra[row][col];
    }

    private final int dijkstraGhostScore(final int row, final int col) {
        if (dijkstraGhost == null) {
            dijkstraGhost = new int[map.length][map[indy.row].length];
            for (final int[] part : dijkstraGhost)
                Arrays.fill(part, Integer.MAX_VALUE);
            updateDijkstraGhost(goal.row, goal.col, 0, true);
        }
        if (row < 0 || col < 0 || row >= dijkstra.length || col >= dijkstra[row].length)
            return Integer.MAX_VALUE;
        return dijkstraGhost[row][col];
    }

    private boolean isRockPresent(final int row, final int col) {
        for (final Rock rock : rocks)
            if (rock.isAt(row, col))
                return true;
        return false;
    }

    public boolean isEmpty(final int row, final int col) {
        if (row < 0 || col < 0 || row >= map.length || col >= map[row].length)
            return false;
        return !map[row][col] && !isRockPresent(row, col) && !goal.isAt(row, col);
    }

    public int solve() {
        return solve(0);
    }

    private int solve(final int currentDepth) {
        System.out.println(toString());
        visited.add(this);
        if (isSolved()) {
            setShortestSolution(currentDepth);
            return 0;
        }
        if (currentDepth >= getShortestSolution()) {
            System.out.println("Aborting at depth " + currentDepth + " because we know better: "
                               + getShortestSolution());
            return Integer.MAX_VALUE;
        }
        final Map<Rock, Set<Direction>> nextTries = indy.getMoveableRocks();
        int shortest = Integer.MAX_VALUE - 1;
        for (final Map.Entry<Rock, Set<Direction>> tries : nextTries.entrySet()) {
            final Rock rock = tries.getKey();
            for (final Direction dir : tries.getValue()) {
                final Maze next = new Maze(this, rock, dir);
                if (!isRepeat(next)) {
                    final int nextSolution = next.solve(currentDepth + 1);
                    if (nextSolution < shortest)
                        shortest = nextSolution;
                }
            }
        }
        return shortest + 1;
    }

    public boolean isSolved() {
        return indy.canReachTreasure();
    }

    @Override
    public String toString() {
        if (stringValue == null) {
            final StringBuilder out = new StringBuilder();
            for (int row = 0; row < map.length; row++) {
                if (row == 0) {
                    out.append('\u250C');
                    for (int col = 0; col < map[row].length; col++)
                        out.append('\u2500');
                    out.append("\u2510\n");
                }
                out.append('\u2502');
                for (int col = 0; col < map[row].length; col++) {
                    if (indy.isAt(row, col))
                        out.append('*');
                    else if (goal.isAt(row, col))
                        out.append("$");
                    else if (isRockPresent(row, col))
                        out.append("@");
                    else if (map[row][col])
                        out.append('\u2588');
                    else
                        out.append(base64(dijkstra[row][col]));
                }
                out.append("\u2502\n");
                if (row == map.length - 1) {
                    out.append('\u2514');
                    for (int col = 0; col < map[row].length; col++)
                        out.append('\u2500');
                    out.append("\u2518\n");
                }
            }
            stringValue = out.toString();
        }
        return stringValue;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!obj.getClass().equals(getClass()))
            return false;
        final Maze other = (Maze) obj;
        if (other.map.length != map.length)
            return false;
        for (int row = 0; row < map.length; row++) {
            if (other.map[row].length != map[row].length)
                return false;
            for (int col = 0; col < map[row].length; col++)
                if (other.map[row][col] != map[row][col])
                    return false;
        }
        return indy.equals(other.indy) && rocks.equals(other.rocks) && goal.equals(other.goal);
    }

    @Override
    public int hashCode() {
        return getClass().hashCode() ^ indy.hashCode() ^ goal.hashCode() ^ rocks.hashCode();
    }

    private final class Goal extends PointOfInterest {
        public Goal(final int row, final int col) {
            super(row, col);
        }
    }

    private final class Indy extends PointOfInterest {
        public Indy(final int row, final int col) {
            super(row, col);
        }

        public boolean canReachTreasure() {
            return dijkstraScore(row, col) < Integer.MAX_VALUE;
        }

        public SortedMap<Rock, Set<Direction>> getMoveableRocks() {
            final SortedMap<Rock, Set<Direction>> out = new TreeMap<>();
            @SuppressWarnings("unchecked")
            final Set<Direction> checked[][] = new Set[map.length][map[row].length];
            lookForRocks(out, checked, row, col, null);
            return out;
        }

        private final void lookForRocks(final Map<Rock, Set<Direction>> rockStore,
                                        final Set<Direction>[][] checked,
                                        final int row,
                                        final int col,
                                        final Direction comingFrom) {
            if (row < 0 || col < 0 || row >= checked.length || col >= checked[row].length)
                return;
            if (checked[row][col] == null)
                checked[row][col] = EnumSet.noneOf(Direction.class);
            if (checked[row][col].contains(comingFrom))
                return;
            for (final Rock rock : rocks) {
                if (rock.row == row && rock.col == col) {
                    if (rock.canBeMoved(comingFrom) && rock.isWorthMoving(comingFrom)) {
                        if (!rockStore.containsKey(rock))
                            rockStore.put(rock, EnumSet.noneOf(Direction.class));
                        rockStore.get(rock).add(comingFrom);
                    }
                    return;
                }
            }
            if (comingFrom != null)
                checked[row][col].add(comingFrom);
            for (final Direction dir : Direction.values())
                if (comingFrom == null || dir != comingFrom.opposite())
                    if (isEmpty(row + dir.drow, col + dir.dcol) || isRockPresent(row + dir.drow, col + dir.dcol))
                        lookForRocks(rockStore, checked, row + dir.drow, col + dir.dcol, dir);
        }
    }

    private final class Rock extends PointOfInterest implements Comparable<Rock> {
        public Rock(final int row, final int col) {
            super(row, col);
        }

        public boolean canBeMoved(final Direction direction) {
            return isEmpty(row + direction.drow, col + direction.dcol);
        }

        public boolean isWorthMoving(final Direction direction) {
            boolean worthIt = false;
            boolean reachable = false;
            int emptyAround = 0;
            for (final Direction dir : Direction.values()) {
                reachable |= (dijkstraScore(row, col) < Integer.MAX_VALUE);
                emptyAround += (isEmpty(row + dir.drow, col + dir.dcol) ? 1 : 0);
                if (dir != direction && dir != direction.opposite()
                    && dijkstraScore(row + dir.drow, col + dir.dcol) < Integer.MAX_VALUE)
                    worthIt = true;
            }
            return (emptyAround < 4) && (worthIt || !reachable);
        }

        public int proximityIndice() {
            final int ds = min(dijkstraScore(row - 1, col),
                               dijkstraScore(row + 1, col),
                               dijkstraScore(row, col - 1),
                               dijkstraScore(row, col + 1));
            if (ds < Integer.MAX_VALUE)
                return ds;
            else
                return min(dijkstraGhostScore(row - 1, col),
                           dijkstraGhostScore(row + 1, col),
                           dijkstraGhostScore(row, col - 1),
                           dijkstraGhostScore(row, col + 1));
        }

        @Override
        public int compareTo(Rock o) {
            return new Integer(proximityIndice()).compareTo(o.proximityIndice());
        }
    }

    private static final char base64(final int i) {
        if (i >= 0 && i <= 9)
            return (char) ('0' + i);
        else if (i < 36)
            return (char) ('A' + (i - 10));
        else
            return ' ';
    }

    private static final int min(final int i1, final int i2, final int... in) {
        int min = Math.min(i1, i2);
        for (final int i : in)
            min = Math.min(min, i);
        return min;
    }
}

답변

EMPTY = '0'
WALL = '1'
INDY = '2'
GOAL = '3'
ROCK = '4'

map=%q|8 8
00001000
00000100
00000010
00000010
03004040
10000010
10000100
10000102|

def deep_dup(arr)
  dupl = arr.dup
  (0..dupl.size-1).to_a.each do |i|
    dupl[i] = dupl[i].dup
  end
  return dupl
end

class Map
  @@visited = []
  attr_reader :mapdata, :indy_r, :indy_c, :prev

  def self.parse(str)
    lines = str.split("\n")
    mapdata = []
    indy_r = -1
    indy_c = -1
    lines[1..-1].each_with_index do |line, idx|
      row = ((mapdata ||= [])[idx] ||= [])
      line.split(//).each_with_index do |c, cidx|
        if c==INDY
          indy_r = idx
          indy_c = cidx
          row[cidx] = EMPTY
        else
          row[cidx] = c
        end
      end
    end
    return Map.new(mapdata, indy_r, indy_c)
  end

  def initialize(mapdata, indy_r, indy_c, prev = nil, pushed = false)
    @mapdata = mapdata
    @mapdata.freeze
    @mapdata.each {|x| x.freeze}
    @indy_r = indy_r
    @indy_c = indy_c
    @prev = prev
    @pushed = pushed
  end

  def visit!
    @@visited << self
  end

  def visited?
    @@visited.include?(self)
  end

  def pushes
    pushes = @pushed ? 1 : 0
    if @prev
      pushes += @prev.pushes
    end
    return pushes
  end

  def history
    return @prev ? 1+@prev.history : 0
  end

  def next_maps
    maps = []
    [[-1, 0], [1, 0], [0, -1], [0, 1]].each do |dr, dc|
      new_i_r = self.indy_r + dr
      new_i_c = self.indy_c + dc
      if new_i_r >= 0 && new_i_r < @mapdata.size && new_i_c >= 0 && new_i_c < @mapdata[0].size
        new_map = nil
        pushed = false
        case @mapdata[new_i_r][new_i_c]
        when EMPTY, GOAL then new_map = @mapdata
        when ROCK then
          if @mapdata[new_i_r+dr] && @mapdata[new_i_r+dr][new_i_c+dc] == EMPTY
            new_map = deep_dup(@mapdata)
            new_map[new_i_r][new_i_c] = EMPTY
            new_map[new_i_r+dr][new_i_c+dc] = ROCK
            pushed = true
          end
        end
        if new_map && !@@visited.include?(new_map = Map.new(new_map, new_i_r, new_i_c, self, pushed))
          maps << new_map
        end
      end
    end
    return maps
  end

  def wins?
    return @mapdata[@indy_r][@indy_c] == GOAL
  end

  def to_s
    str = ''
    @mapdata.each_with_index do |row, r|
      row.each_with_index do |col, c|
        if r == @indy_r and c == @indy_c then
          str += 'I'
        else
          case col
          when EMPTY then str += '_'
          when WALL then str+= '#'
          when ROCK then str += 'O'
          when GOAL then str += '$'
          end
        end
      end
      str += "\n"
    end
    return str
  end

  def ==(other)
    return (self.mapdata == other.mapdata) &&
      (self.indy_r == other.indy_r) &&
      (self.indy_c == other.indy_c)
  end

  def dist_to_treasure
    if @distance.nil?
      @mapdata.each_with_index do |r, ri|
        r.each_with_index do |c, ci|
          if c == GOAL
            @distance = Math.sqrt((ri - @indy_r)**2 + (ci - @indy_c)**2)
            return @distance
          end
        end
      end
    end
    return @distance
  end

  def <=>(other)
    dist_diff = self.dist_to_treasure <=> other.dist_to_treasure
    if dist_diff != 0
      return dist_diff
    else
      return self.pushes <=> other.pushes
    end
  end
end

scored = nil
root = Map.parse(map)
to_visit = [root]
until to_visit.empty?
  state = to_visit.pop
  next if state.visited?
  if state.wins? && (scored.nil? || scored.pushes > state.pushes)
    scored = state
  end
  state.visit!
  to_visit += state.next_maps
  to_visit.reject! {|x| x.visited? || (scored && scored.pushes <= x.pushes) }
  to_visit.sort!
  to_visit.reverse!
end

puts scored ? scored.pushes : 'X'
exit(0) unless scored
steps = [scored]
curr = scored
while curr = curr.prev
  steps << curr
end
puts "\nDetails of the path:"
steps.reverse.each_with_index do |step, idx|
  puts "Step ##{idx} (history: #{step.history}, pushes so far: #{step.pushes})"
  puts step
  puts
end

Map#         : 0 1 2 3 4 5 12 15 19 T1 T2 T3 T4 T5 T6 T7
C++  (foobar): O O O O O O  O  O  O  O  O  O  ?  O  ?  O
Ruby (Romain): X O O ? O O  O  X  ?  ?  O  ?  ?  ?  ?  ?
Java (Romain): O O X O X X  O  O  ?  ?  O  O  O  X  O  O

#include <vector>
#include <iostream>
#include <iterator>
#include <sstream>
#include <unordered_set>
#include <utility>

enum class dir : char {
    up, down, left, right
};

enum class field : char {
    floor, wall, indiana, treasure, rock, border, visited
};

class pos {
    private:
        int x, y;
        field f_type;


    public:
        pos() : x{-1}, y{-1}, f_type{field::border} {}
        pos(int x, int y, field f_type) : x{x}, y{y}, f_type{f_type} {}

        const field& get() {
            return f_type;
        }

        friend class map;
        friend class move;

        bool operator==(const pos& other) const {
            return x == other.x && y == other.y && f_type == other.f_type;
        }
};

class move {
    private:
        pos position;
        dir direction;

    public:
        move(pos& position, dir&& direction) : position(position), direction(direction) {}

        bool operator==(const move& other) const {
            return position == other.position && direction == other.direction;
        }

        int int_value() const {
            return static_cast<char>(direction) + position.x + position.y + static_cast<char>(position.f_type);
        }

        std::string str() const;

        friend class map;
};

std::string move::str() const {
    std::string direction_str;
    switch(direction) {
        case dir::up: direction_str = "up"; break;
        case dir::down: direction_str = "down"; break;
        case dir::left: direction_str = "left"; break;
        case dir::right: direction_str = "right"; break;
    }
    std::ostringstream oss{};
    oss << "move x" << position.x << " y" << position.y << " " << direction_str;
    return oss.str();
}

std::ostream& operator<<(std::ostream& os, const move& move_object) {
    return os << move_object.str();
}


namespace std {
    template<> struct hash< ::move> {
        size_t operator()(const ::move& o) const {
            return hash<int>()(o.int_value());
        }
    };
}


class constellation {
    private:
        const std::unordered_set<move> moves;

    public:
        constellation(const std::unordered_set<move>& moves) : moves(moves) {}

        bool operator==(const constellation& other) const {
            if (moves.size() != other.moves.size()) return false;
            for (auto i = moves.begin(); i != moves.end(); ++i) {
                if (!other.moves.count(*i)) return false;
            }
            return true;
        }

        int int_value() const {
            int v = 0;
            for (auto i = moves.begin(); i != moves.end(); ++i) {
                v += i->int_value();
            }
            return v;
        }
};

namespace std {
    template<> struct hash< ::constellation> {
        size_t operator()(const ::constellation& o) const {
            return hash<int>()(o.int_value());
        }
    };
}


class map {

    private:
        pos* previous;
        pos start, border;
        std::vector< std::vector<pos> > rep;
        void init(const std::string&);

    public:
        map(std::istream& input) : previous{} {
            init(static_cast<std::stringstream const&>(std::stringstream() << input.rdbuf()).str());
        }

        map& move(const move& m) {
            pos source = m.position;
            pos& target = get(source, m.direction);
            target.f_type = source.f_type;
            source.f_type = field::indiana;
            rep[start.y][start.x].f_type = field::floor;
            start = source;
            rep[start.y][start.x].f_type = field::indiana;
            return *this;
        }

        std::string str() const;

        pos& get() { return start; }

        pos& get(pos& position, const dir& direction) {
            int tx = position.x, ty = position.y;
            switch(direction) {
                case dir::up: --ty; break;
                case dir::down: ++ty; break;
                case dir::left: --tx; break;
                case dir::right: ++tx; break;
            }
            previous = &position;
            if (tx >= 0 && ty >= 0 && static_cast<int>(rep.size()) > ty && static_cast<int>(rep[ty].size()) > tx) {
                pos& tmp = rep[ty][tx];
                return tmp;
            }
            border.x = tx;
            border.y = ty;
            return border;
        }

        pos& prev() {
            return *previous;
        }

        void find_moves(std::unordered_set< ::move>& moves, bool& finished) {
            map copy = *this;
            auto& rep = copy.rep;
            bool changed = true;

            while (changed) {
                changed = false;
                for (auto row = rep.begin(); row != rep.end(); ++row) {
                    for (auto col = row->begin(); col != row->end(); ++col) {
                        // check if the field is of interest
                        if (col->f_type == field::floor || col->f_type == field::treasure || col->f_type == field::rock) {
                            // get neighbours
                            pos& up = copy.get(*col, dir::up);
                            pos& down = copy.get(*col, dir::down);
                            pos& left = copy.get(*col, dir::left);
                            pos& right = copy.get(*col, dir::right);
                            // ignore uninteresting rocks
                            if (col->f_type == field::rock && (up.f_type == field::floor || up.f_type == field::indiana || up.f_type == field::visited) && (down.f_type == field::floor || down.f_type == field::indiana || down.f_type == field::visited) && (left.f_type == field::floor || left.f_type == field::indiana || left.f_type == field::visited) && (right.f_type == field::floor || right.f_type == field::indiana || right.f_type == field::visited)) {
                                pos& upper_left = copy.get(up, dir::left);
                                pos& lower_left = copy.get(down, dir::left);
                                pos& upper_right = copy.get(up, dir::right);
                                pos& lower_right = copy.get(down, dir::right);
                                if ((upper_left.f_type == field::floor || upper_left.f_type == field::indiana || upper_left.f_type == field::visited) && (lower_left.f_type == field::floor || lower_left.f_type == field::indiana || lower_left.f_type == field::visited) && (upper_right.f_type == field::floor || upper_right.f_type == field::indiana || upper_right.f_type == field::visited) && (lower_right.f_type == field::floor || lower_right.f_type == field::indiana || lower_right.f_type == field::visited)) {
                                    continue;
                                }
                            }
                            // check if the field can be reached
                            if (up.f_type == field::visited || up.f_type == field::indiana) {
                                if (col->f_type == field::rock && (down.f_type == field::visited || down.f_type == field::floor || down.f_type == field::indiana)) {
                                    auto insertion = moves.insert( ::move(*col, dir::down));
                                    if (insertion.second) {
                                        changed = true;
                                    }
                                }
                                else if (col->f_type == field::floor) {
                                    changed = true;
                                    col->f_type = field::visited;
                                }
                                else if (col->f_type == field::treasure) {
                                    finished = true;
                                    return;
                                }
                            }
                            if (down.f_type == field::visited || down.f_type == field::indiana) {
                                if (col->f_type == field::rock && (up.f_type == field::visited || up.f_type == field::floor || up.f_type == field::indiana)) {
                                    auto insertion = moves.insert( ::move(*col, dir::up));
                                    if (insertion.second) {
                                        changed = true;
                                    }
                                }
                                else if (col->f_type == field::floor) {
                                    changed = true;
                                    col->f_type = field::visited;
                                }
                                else if (col->f_type == field::treasure) {
                                    finished = true;
                                    return;
                                }
                            }
                            if (left.f_type == field::visited || left.f_type == field::indiana) {
                                if (col->f_type == field::rock && (right.f_type == field::visited || right.f_type == field::floor || right.f_type == field::indiana)) {
                                    auto insertion = moves.insert( ::move(*col, dir::right));
                                    if (insertion.second) {
                                        changed = true;
                                    }
                                }
                                else if (col->f_type == field::floor) {
                                    changed = true;
                                    col->f_type = field::visited;
                                }
                                else if (col->f_type == field::treasure) {
                                    finished = true;
                                    return;
                                }
                            }
                            if (right.f_type == field::visited || right.f_type == field::indiana) {
                                if (col->f_type == field::rock && (left.f_type == field::visited || left.f_type == field::floor || left.f_type == field::indiana)) {
                                    auto insertion = moves.insert( ::move(*col, dir::left));
                                    if (insertion.second) {
                                        changed = true;
                                    }
                                }
                                else if (col->f_type == field::floor) {
                                    changed = true;
                                    col->f_type = field::visited;
                                }
                                else if (col->f_type == field::treasure) {
                                    finished = true;
                                    return;
                                }
                            }
                        }
                    }
                }
            }
        }

};

void map::init(const std::string& in) {
    bool first = true;

    for(auto i = in.begin(); i != in.end(); ++i) {
        if (*i == '\n') {
           first = false;
            rep.push_back({});
            continue;
        }
        else if (first) continue;

        field tmp(static_cast<field>(*i - '0'));
        pos current(rep.back().size(), rep.size() - 1, tmp);
        switch(tmp) {
            case field::indiana:
                start = current;
            case field::floor:
            case field::wall:
            case field::treasure:
            case field::rock:
                rep.back().push_back(current);
                break;
            default: std::cerr << "Invalid field value '" << (char) (static_cast<char>(tmp) + 48) << '\'' << std::endl;
        }
    }
}

std::string map::str() const {
    std::string t{};
    for (auto row = rep.begin(); row != rep.end(); ++row) {
        for (auto col = row->begin(); col != row->end(); ++col) {
            t += static_cast<char>(col->f_type) + '0';
        }
        t += '\n';
    }
    return t;
}

std::ostream& operator<<(std::ostream& os, const map& map_object) {
    return os << map_object.str();
}

int solve(map&& data) {
    int moves_taken = -1;
    bool finished = false;
    std::vector<map> current_maps{data}, next_maps;
    std::unordered_set<constellation> known_constellations;

    while (!finished && !current_maps.empty()) {
        for (auto i = current_maps.begin(); i != current_maps.end(); ++i) {
            std::unordered_set<move> moves;
            i->find_moves(moves, finished);
            auto result = known_constellations.insert(constellation(moves));
            if (!result.second) {
                continue; // this map constellation was already seen. prevent loops...
            }

            if (finished) break;
            for (auto m = moves.begin(); m != moves.end(); ++m) {
                map map_copy = *i;
                map_copy.move(*m);
                next_maps.push_back(map_copy);
            }


        }
        ++moves_taken;
        current_maps = std::move(next_maps);
    }
    if (!finished && current_maps.empty()) return -1;
    return moves_taken;
}

int main(int argc, char* argv[]) {
    map data{std::cin};

    int moves_taken = solve(std::move(data));
    if (moves_taken == -1) std::cout << "X" << std::endl;
    else std::cout << moves_taken << std::endl;

    return 0;
}