Untitled
fttk2
plain_text
25 days ago
4.3 kB
2
Indexable
Never
package main; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.*; class State { int[][] map; int playerX, playerY; int boxX, boxY; int pushes; public State(int[][] map, int playerX, int playerY, int boxX, int boxY, int pushes) { this.map = map; this.playerX = playerX; this.playerY = playerY; this.boxX = boxX; this.boxY = boxY; this.pushes = pushes; } } public class SokobanSolver { private static final int[] dx = {0, 0, -1, 1}; private static final int[] dy = {-1, 1, 0, 0}; static int solve(int[][] map, int playerX, int playerY, int boxX, int boxY, int targetX, int targetY) { PriorityQueue<State> priorityQueue = new PriorityQueue<>((a, b) -> a.pushes - b.pushes); Set<String> visited = new HashSet<>(); int rows = map.length; int cols = map[0].length; priorityQueue.offer(new State(map, playerX, playerY, boxX, boxY, 0)); while (!priorityQueue.isEmpty()) { State current = priorityQueue.poll(); if (current.boxX == targetX && current.boxY == targetY) { return current.pushes; // Minimum number of pushes to reach the goal } visited.add(current.boxX + "-" + current.boxY + "-" + current.playerX + "-" + current.playerY); for (int i = 0; i < 4; i++) { int newPlayerX = current.playerX + dx[i]; int newPlayerY = current.playerY + dy[i]; if (newPlayerX < 0 || newPlayerX >= rows || newPlayerY < 0 || newPlayerY >= cols) { continue; } if (current.map[newPlayerX][newPlayerY] == 1) { continue; } if (visited.contains(current.boxX + "-" + current.boxY + "-" + newPlayerX + "-" + newPlayerY)) { continue; } int[][] newMap = new int[rows][cols]; for (int j = 0; j < rows; j++) { for (int k = 0; k < cols; k++) { newMap[j][k] = current.map[j][k]; } } int newBoxX = current.boxX; int newBoxY = current.boxY; int push = current.pushes; if (current.boxX == newPlayerX && current.boxY == newPlayerY) { newBoxX += dx[i]; newBoxY += dy[i]; if (newBoxX < 0 || newBoxX >= rows || newBoxY < 0 || newBoxY >= cols || newMap[newBoxX][newBoxY] == 1) { continue; } newMap[current.boxX][current.boxY] = 0; newMap[newBoxX][newBoxY] = 2; push++; } newMap[current.playerX][current.playerY] = 0; newMap[newPlayerX][newPlayerY] = 3; priorityQueue.offer(new State(newMap, newPlayerX, newPlayerY, newBoxX, newBoxY, push)); } } return -1; // No solution found } public static void main(String[] args) throws FileNotFoundException { // Define the Sokoban map, player, box, and target positions using integers (1 for walls, 0 for empty spaces). System.setIn(new FileInputStream("input.txt")); Scanner sc = new Scanner(System.in); int[][] map = new int [10][10]; for(int i=0; i<10; i++) { for(int j=0; j<10; j++) { map[i][j] = sc.nextInt(); } } int boxX = 4; int boxY = 7; int playerX = 4; int playerY = 8; int targetX = 2; int targetY = 8; int pushes = solve(map, playerX, playerY, boxX, boxY, targetX, targetY); if (pushes >= 0) { System.out.println("Minimum pushes required: " + pushes); } else { System.out.println("No solution found."); } } } 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1