История

Индиана Джонс исследовала пещеру, где находится драгоценное сокровище. Внезапно произошло землетрясение.

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

Ваша цель - помочь Индиане Джонсу получить сокровище. Поскольку толкнуть даже один камень очень сложно, количество толчков очень важно.

проблема

Найдите лучший способ (где Индиана Джонс толкает камни как можно меньше), чтобы найти сокровище.

Карта (вход)

Отображение является mпутем n(как больше , чем 1) матрицы , которая может содержать пять видов ячейки:

• 0 что означает пустую клетку,
• 1 что означает стену,
• 2 в которой находится Индиана Джонс (существует только одна),
• 3 в котором находится сокровище (существует только одно),
• и 4, что означает камень.

В первом ряду карты размер карты указан примерно так же 4 6, а во втором ряду до последнего ряда карты структура пещеры определена примерно так.

110131
104040
100101
200000

Следовательно, полная карта:

4 6
110131
104040
100101
200000

что значит

Карта дается с помощью стандартного ввода, файла (вы можете указать имя файла) или массива в коде, который содержит только вышеуказанную информацию.

Выход

Минимальное количество Индиана Джонс должен подтолкнуть. Если такого способа нет, выведите X.

В приведенном выше случае он может толкнуть камень влево вверх, затем он может толкнуть камень вправо вправо, чтобы получить сокровище. Поэтому выход в этом случае есть 2.

Тем не мение. в этом случае :

4 6
111131
104040
100101
200000

(смотрите ниже) он не может толкнуть правый камень, потому что он уничтожит сокровище. Кроме того, нажатие на левый камень вправо ничего не меняет. Поэтому на выходе есть X.

правила

• Он может двигаться только в четырех направлениях: вверх, вниз, влево и вправо.
• Он не может толкнуть два последовательных камня .
• Он не может тянуть любой камень, и он может толкать камень только в одном направлении («вперед»).
• Он не может пройти сквозь стены. Только места, куда он может пойти, - это пустые клетки и ячейка с сокровищами.
• Камень нельзя положить на клад. Это уничтожит сокровище. :(
• Он не может выйти за пределы карты.

цели

Программа, которая может обрабатывать большинство карт (предоставленных в разделе «Пример» + другие) в разумные сроки (в частности, 10 секунд) и выдает правильный ответ.

Здесь «другие» означает пример входных данных, представленных в ответах. Это означает, что вы должны создать умный алгоритм, чтобы другие программы не могли решать карты, которые может решить ваша программа, а карты, решаемые другими программами, могут быть решены вашей программой. Однако размещение решений в коде не будет считаться действительным.

Заметка

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

Было сказано, что эта проблема является NP, но также было сказано, что хороший эвристический алгоритм может решить проблему довольно эффективно. Я использовал некоторые идеи и эвристики для эффективного решения проблемы, и мой код мог очень быстро найти все решения примеров (менее чем за секунду).

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

Поскольку я уже завершил проект (кстати, изображения не мои - я их погуглил), вам не нужно об этом беспокоиться.

Примеры

Примеры можно увидеть здесь. Вы также можете посмотреть примеры и проверить свои результаты здесь (это должно работать в современных браузерах). Вы можете получить карту в формате, описанном выше, набрав whatisthis()в консоли JS.

http://bit.sparcs.org/~differ/sokoban/#0 ~ http://bit.sparcs.org/~differ/sokoban/#19 содержит примеры, которые изначально были предоставлены классом.

Результат

Извините, я опоздал .. довольно много на самом деле. : P (Мне было лень забивать. Извините.)

Ниже приведен результат. (X: неправильно, O: правильно,?: Занимает не менее 10 секунд, остановлено)

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

(Java 19: 25 секунд, результат был правильным.) (Я использовал ruby ​​1.9.3 и javac 1.7.0_13)

Кажется, что алгоритм Java действительно был лучше. (Кстати, я подумал о похожем методе, но понял, что существуют карты, подобные тестовой карте 5).

Java - немного умнее / быстрее

Там немного кода. Я пытаюсь быть быстрее, оценивая толчки в порядке «какова вероятность того, что это освободит путь к сокровищам», который сам основан на двух обходах Дейкстры (один останавливается при встрече с камнями, другой игнорирует камни). Он работает довольно хорошо, и один пример из pastebin, который кажется проблематичным для автора, решается примерно за 2 секунды этой реализацией. Некоторые другие примеры занимают до 30-40 секунд, что я все еще нахожу слишком длинным, но я не мог найти способ улучшить это, не ломая вещи :)

Я разбил свои вещи на несколько файлов, чтобы получить лучшую структуру (а также почему я перешел на Java с ruby):

Входная точка:

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:

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

Редактировать: Я думаю о способах значительно улучшить производительность этого в неочевидных ситуациях (где это в настоящее время сосет зеленые яйца), отбрасывая простую оценку движения (например, заботиться только о том, когда инди толкает камни и / или добирается до сокровища). Я, вероятно, обновлю код позже, когда у меня будет время для реализации.

C ++ 14 из 16

Алгоритм неэффективен и требует много памяти. Кроме того, я не мог позволить себе время, чтобы привести его в порядок, но у меня будет время, когда у меня будет больше времени;) Интересно то, что мой алгоритм дает сбой на тех же тестовых картах, что и спрашивающий. На моей древней записной книжке процесс начинается подмена карт Т4 и Т6. Карта 3 занимает довольно много времени, но решается вовремя. Все остальные решаются практически мгновенно. Поэтому мне придется выяснить, как решить T4 и T6 и попробовать алгоритм на машине с большим объемом памяти. В конце концов я могу решить T4 и T6 там. Я буду держать пост в курсе ...

Ниже приведен результат. (X: неправильно, O: правильно,?: Занимает не менее 10 секунд, остановлено)

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

Поскольку исходный код довольно длинный и не очень приятный для чтения ... В основном он просто ищет все камни, которые могут быть найдены Индианой Джонсом. Для камней, которые могут быть достигнуты, он хранит информацию о том, в каких направлениях он может быть перемещен. Итак, список возможных ходов для текущей карты создан. Для каждого из этих возможных ходов создается копия карты и применяется ход. Для вновь созданных карт, алгоритм снова проверит, какие ходы можно применить ... Это делается до тех пор, пока не будут выполнены никакие дальнейшие ходы или пока не найден путь к сундуку с сокровищами. Поскольку алгоритм сначала пробует все ходы, для достижения которых требуется только одно движение, затем все, что занимает два, и так далее ... первый найденный путь также автоматически становится самым коротким. Для предотвращения зацикливания алгоритм запоминает для каждой карты, какие движения можно применить. Если создается другая карта, которая приводит к списку ходов, которые уже были найдены ранее, они автоматически отбрасываются, поскольку они уже обрабатываются. К сожалению, невозможно выполнить каждое движение только один раз, поскольку могут быть карты, требующие перемещения камня по одному и тому же полю несколько раз. В противном случае я мог бы сэкономить много памяти. Кроме того, для своевременного решения таких карт, как карта 3, алгоритм игнорирует все камни, которые можно обойти ... Так что на карте 3 камень в середине нигде не будет перемещаться, но только до тех пор, пока вокруг него не останется больше стен. Код может быть скомпилирован с g ++ --std = c ++ 0x с g ++ версии 4.4.3 или новее. Невозможно выполнить каждое движение только один раз, поскольку могут быть карты, требующие перемещения камня по одному и тому же полю несколько раз. В противном случае я мог бы сэкономить много памяти. Кроме того, для своевременного решения таких карт, как карта 3, алгоритм игнорирует все камни, которые можно обойти ... Так что на карте 3 камень в середине нигде не будет перемещаться, но только до тех пор, пока вокруг него не останется больше стен. Код может быть скомпилирован с g ++ --std = c ++ 0x с g ++ версии 4.4.3 или новее. Невозможно выполнить каждое движение только один раз, поскольку могут быть карты, требующие перемещения камня по одному и тому же полю несколько раз. В противном случае я мог бы сэкономить много памяти. Кроме того, для своевременного решения таких карт, как карта 3, алгоритм игнорирует все камни, которые можно обойти ... Так что на карте 3 камень в середине нигде не будет перемещаться, но только до тех пор, пока вокруг него не останется больше стен. Код может быть скомпилирован с g ++ --std = c ++ 0x с g ++ версии 4.4.3 или новее. но только до тех пор, пока вокруг него больше не будет стен. Код может быть скомпилирован с g ++ --std = c ++ 0x с g ++ версии 4.4.3 или новее. но только до тех пор, пока вокруг него больше не будет стен. Код может быть скомпилирован с g ++ --std = c ++ 0x с g ++ версии 4.4.3 или новее.

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

Редактировать: программа берет свой ввод из стандартного ввода и игнорирует первую строку, содержащую размер карты. Он проверяет, используются ли на карте только разрешенные символы, но не проверяет, что есть только одна Индиана Джонс и один сундук с сокровищами. Таким образом, можно разместить более одного, и на стандартный вывод выводится наименьшее количество ходов, необходимых для достижения одного из сундуков. Любые недопустимые символы на карте будут пропущены, и программа попытается вычислить наименьшее количество ходов для полученной карты. Расчет начнется при закрытии стандартного ввода (в моей системе Ctrl + D).