인디애나 존스가 보물을 얻도록 도와주세요 존스가 위치한

이야기

인디애나 존스는 소중한 보물이있는 동굴을 탐험하고있었습니다. 갑자기 지진이 일어났습니다.

지진이 끝났을 때, 그는 천장에서 떨어진 일부 바위가 보물로가는 길을 막았다는 것을 알았습니다. 그는 돌을 밀 수 있다는 것을 알아 차 렸지만 돌이 무겁기 때문에 두 개의 연속 돌을 밀 수 없었습니다 .

귀하의 목표는 인디아나 존스가 보물을 얻도록 돕는 것입니다. 하나의 석재조차 밀어 내기가 매우 어렵 기 때문에 푸시 횟수가 매우 중요합니다.

문제

보물을 찾기 위해 가장 좋은 방법을 찾으십시오 (인디아나 존스가 돌을 가능한 한 적게 밉니다).

지도 (입력)

지도는 5 가지 종류의 셀을 포함 할 수 있는 mby n(1보다 큰) 행렬입니다.

  • 0 빈 셀을 의미합니다.
  • 1 벽을 의미하고
  • 2 인디애나 존스가 위치한 곳 (하나만 존재)
  • 3 보물이있는 곳 (하나만 존재)
  • 그리고 4이것은 바위를 의미합니다.

맵의 첫 번째 행에서 맵의 차원은 다음과 같이 지정되고 맵 4 6의 두 번째 행에서 마지막 행까지는 동굴 구조가 이와 같이 지정됩니다.

110131
104040
100101
200000

따라서 전체지도는 다음과 같습니다.

4 6
110131
104040
100101
200000

그 의미는

지도

맵은 stdin, 파일 (파일 이름을 지정할 수 있음) 또는 위 정보 만 포함 된 코드의 배열로 제공됩니다.

산출

인디애나 존스가 최소한으로 밀어 붙여야합니다. 그런 방법이 없다면 output X.

위의 경우 왼쪽에서 돌을 위로 밀고 오른쪽으로 돌을 밀어 보물을 얻을 수 있습니다. 따라서이 경우 출력은 2입니다.

하나. 이 경우 :

4 6
111131
104040
100101
200000

그는 보물을 파괴 할 것이기 때문에 오른쪽 돌을 밀 수 없습니다. 또한 왼쪽 돌을 오른쪽으로 밀면 아무것도 변하지 않습니다. 따라서 출력은 X입니다.

규칙

  • 그는 위, 아래, 왼쪽 및 오른쪽의 네 방향으로 만 움직일 수 있습니다.
  • 그는 두 개의 연속 돌을 밀 수 없습니다 .
  • 그는 돌을 당길 수 없으며 돌을 한 방향으로 만 움직일 수 있습니다 ( ‘앞으로’).
  • 그는 벽을 통과 할 수 없습니다. 그가 갈 수있는 곳은 빈 칸과 보물 칸뿐입니다.
  • 보물 위에 돌을 놓을 수 없습니다. 보물을 파괴합니다. 🙁
  • 그는지도 밖으로 나갈 수 없습니다.

목표

적당한 시간 (특히 10 초)에 가장 많은지도 ( ‘예’섹션 + 기타에 제공)를 처리하고 정답을 출력하는 프로그램입니다.

여기서 ‘기타’는 답변에 제공된 입력 예를 의미합니다. 즉, 다른 프로그램에서 프로그램이 해결할 수있는 맵을 해결할 수없고 다른 프로그램으로 해결 된 맵을 프로그램에서 해결할 수 있도록 스마트 알고리즘을 만들어야합니다. 그러나 코드에 솔루션을 넣는 것은 유효한 것으로 간주되지 않습니다.

노트

이것은 원래 제가 들었던 AI 클래스의 중기 프로젝트였습니다. 단 한 가지가 달랐습니다. 두 개의 암석 만 있다고합니다 .

이 문제는 NP라고 말했지만 좋은 휴리스틱 알고리즘으로 문제를 매우 효율적으로 해결할 수 있다고합니다. 문제를 효율적으로 해결하기 위해 몇 가지 아이디어와 휴리스틱을 사용했으며 내 코드는 샘플의 모든 솔루션을 매우 빠르게 찾을 수 있습니다 (1 초 미만).

그러나 두 개 이상의 암석이 있었을 때 적절한 시간 내에 코드에서 답을 찾지 못한 경우가있었습니다. 나는 몇 가지 아이디어를 가지고 있었지만 그중 일부는 ‘잘못된’이고 코드에 다른 아이디어를 표현할 수 없었습니다. 이 문제를 해결하기 위해 어떤 스마트 알고리즘이 있는지 알고 싶었습니다.

이미 프로젝트를 완료 했기 때문에 (btw, 이미지는 내 것이 아닙니다-나는 구글 검색했습니다), 당신은 그것에 대해 걱정할 필요가 없습니다.

여기에서 예를 볼 수 있습니다. 여기 에서 예제를보고 결과를 테스트 할 수도 있습니다 (이는 최신 브라우저에서 작동 함). 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

(자바 19 : 25 대가 걸리고 결과가 정확했습니다.) (루비 1.9.3 및 javac 1.7.0_13을 사용했습니다)

Java 알고리즘이 실제로 더 나은 것으로 보입니다. (그런데 비슷한 방법을 생각했지만 테스트 맵 5와 같은 맵이 있음을 깨달았습니다.)



답변

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

꽤 많은 코드가 있습니다. 나는 두 개의 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

편집 : 간단한 움직임 평가를 삭제하여 명백하지 않은 상황 (현재 녹색 알을 빨아 먹는 곳) 에서이 성능을 크게 향상시킬 수있는 방법이 있습니다 (예 : 인디가 바위를 밀거나 보물을 얻을 때만 신경 쓰십시오). 구현할 시간이 있으면 나중에 코드를 업데이트 할 것입니다.


답변

C ++ 14/16 중

알고리즘이 비효율적이고 메모리가 부족합니다. 또한 정리할 시간이 없었지만 더 많은 시간이 있으면 더 할 것입니다.) 흥미로운 점은 내 알고리즘이 질문자와 동일한 테스트 맵에서 실패한다는 것입니다. 고대 노트북에서 프로세스가 T4 및 T6 맵으로 교체되기 시작합니다. 지도 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

소스 코드는 꽤 길고 읽기가 좋지 않기 때문에 기본적으로 Indiana Jones가 도달 할 수있는 모든 암석을 찾습니다. 도달 할 수있는 암석의 경우 이동 가능한 방향 정보를 저장합니다. 따라서 현재지도에 가능한 이동 목록이 만들어집니다. 이러한 각 이동에 대해 맵 사본이 작성되고 이동이 적용됩니다. 새로 생성 된 맵의 경우 알고리즘은 적용 할 수있는 이동을 다시 확인합니다. 이것은 더 이상 이동이 불가능하거나 보물 상자로가는 길을 찾을 때까지 수행됩니다. 알고리즘은 먼저 가슴에 도달하기 위해 한 번의 움직임 만 필요한 모든 움직임을 시도하고, 두 번 걸리는 모든 동작을 시도합니다. 발견 된 첫 번째 방법은 자동으로 가장 짧습니다. 루프를 방지하기 위해 알고리즘은 모든 맵에 어떤 움직임이 적용될 수 있는지 기억합니다. 이전에 이미 발견 된 이동 목록을 생성하는 다른 맵이 작성되면, 이미 처리 중이므로 자동으로 삭제됩니다. 불행히도 같은 필드 위로 여러 번 바위를 이동해야하는지도가있을 수 있으므로 모든 이동을 한 번만 실행할 수는 없습니다. 그렇지 않으면 많은 메모리를 절약 할 수 있습니다. 또한 맵 3과 같은 맵을 제 시간에 해결하기 위해 알고리즘은 걸어 다닐 수있는 모든 암석을 무시합니다. 따라서 맵 3에서는 중간에있는 암석이 움직이고 주변 벽이 없을 때까지만 움직입니다. 코드는 g ++ 버전 4.4.3 이상에서 g ++ –std = c ++ 0x로 컴파일 할 수 있습니다. 같은 필드 위로 여러 번 바위를 이동해야하는지도가있을 수 있으므로 모든 이동을 한 번만 실행할 수는 없습니다. 그렇지 않으면 많은 메모리를 절약 할 수 있습니다. 또한 맵 3과 같은 맵을 제 시간에 해결하기 위해 알고리즘은 걸어 다닐 수있는 모든 암석을 무시합니다. 따라서 맵 3에서는 중간에있는 암석이 움직이고 주변 벽이 없을 때까지만 움직입니다. 코드는 g ++ 버전 4.4.3 이상에서 g ++ –std = c ++ 0x로 컴파일 할 수 있습니다. 같은 필드 위로 여러 번 바위를 이동해야하는지도가있을 수 있으므로 모든 이동을 한 번만 실행할 수는 없습니다. 그렇지 않으면 많은 메모리를 절약 할 수 있습니다. 또한 맵 3과 같은 맵을 제 시간에 해결하기 위해 알고리즘은 걸어 다닐 수있는 모든 암석을 무시합니다. 따라서 맵 3에서는 중간에있는 암석이 움직이고 주변 벽이 없을 때까지만 움직입니다. 코드는 g ++ 버전 4.4.3 이상에서 g ++ –std = c ++ 0x로 컴파일 할 수 있습니다. 그러나 주위에 더 이상 벽이 없을 때까지만. 코드는 g ++ 버전 4.4.3 이상에서 g ++ –std = c ++ 0x로 컴파일 할 수 있습니다. 그러나 주위에 더 이상 벽이 없을 때까지만. 코드는 g ++ 버전 4.4.3 이상에서 g ++ –std = c ++ 0x로 컴파일 할 수 있습니다.

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

편집 : 프로그램은 stdin에서 입력을 가져와 맵 크기가 포함 된 첫 번째 줄을 무시합니다. 맵에서 허용되는 문자 만 사용되는지 확인하지만 인디애나 존스와 보물 상자가 하나만 있는지 확인하지는 않습니다. 따라서 둘 이상을 배치 할 수 있으며 가슴 중 하나에 도달하는 데 필요한 최소 움직임이 표준 출력으로 인쇄됩니다. 맵에서 유효하지 않은 문자는 건너 뛰고 프로그램은 결과 맵에 대한 최소 이동량을 계산하려고 시도합니다. stdin이 닫히면 계산이 시작됩니다 (시스템 Ctrl + d에서).


답변