이야기
인디애나 존스는 소중한 보물이있는 동굴을 탐험하고있었습니다. 갑자기 지진이 일어났습니다.
지진이 끝났을 때, 그는 천장에서 떨어진 일부 바위가 보물로가는 길을 막았다는 것을 알았습니다. 그는 돌을 밀 수 있다는 것을 알아 차 렸지만 돌이 무겁기 때문에 두 개의 연속 돌을 밀 수 없었습니다 .
귀하의 목표는 인디아나 존스가 보물을 얻도록 돕는 것입니다. 하나의 석재조차 밀어 내기가 매우 어렵 기 때문에 푸시 횟수가 매우 중요합니다.
문제
보물을 찾기 위해 가장 좋은 방법을 찾으십시오 (인디아나 존스가 돌을 가능한 한 적게 밉니다).
지도 (입력)
지도는 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에서).