Untitled

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