Scribd
Upload
3 views3 pages

Java Sofa Placement Problem Solution

The Java program implements a solution to the 'Sofa Problem' using breadth-first search (BFS). It defines a State class to represent the position and orientation of a sofa on a grid, and processes input to identify starting and goal positions. The program calculates the minimum number of moves required to transition from the starting state to the goal state, considering possible movements and rotations of the sofa.

Uploaded by

kathir9344853902
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
3 views3 pages

Java Sofa Placement Problem Solution

The Java program implements a solution to the 'Sofa Problem' using breadth-first search (BFS). It defines a State class to represent the position and orientation of a sofa on a grid, and processes input to identify starting and goal positions. The program calculates the minimum number of moves required to transition from the starting state to the goal state, considering possible movements and rotations of the sofa.

Uploaded by

kathir9344853902
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

import [Link].

*;

public class SofaProblem {


static class State {
int r, c; // top-left cell of sofa
boolean horizontal; // true if horizontal, false if vertical

State(int r, int c, boolean horizontal) {


this.r = r;
this.c = c;
[Link] = horizontal;
}

@Override
public boolean equals(Object o) {
if (!(o instanceof State)) return false;
State s = (State) o;
return r == s.r && c == s.c && horizontal == [Link];
}

@Override
public int hashCode() {
return [Link](r, c, horizontal);
}
}

static int M, N;
static char[][] grid;
static State start, goal;

public static void main(String[] args) {


Scanner sc = new Scanner([Link]);
M = [Link]();
N = [Link]();
grid = new char[M][N];

List<int[]> sCells = new ArrayList<>();


List<int[]> SCells = new ArrayList<>();

for (int i = 0; i < M; i++) {


for (int j = 0; j < N; j++) {
grid[i][j] = [Link]().charAt(0);
if (grid[i][j] == 's') [Link](new int[]{i, j});
if (grid[i][j] == 'S') [Link](new int[]{i, j});
}
}

start = buildState(sCells);
goal = buildState(SCells);

int ans = bfs();


if (ans == -1) [Link]("Impossible");
else [Link](ans);
}

static State buildState(List<int[]> cells) {


int r1 = [Link](0)[0], c1 = [Link](0)[1];
int r2 = [Link](1)[0], c2 = [Link](1)[1];
if (r1 == r2) {
int minc = [Link](c1, c2);
return new State(r1, minc, true);
} else {
int minr = [Link](r1, r2);
return new State(minr, c1, false);
}
}

static int bfs() {


Queue<State> q = new LinkedList<>();
Map<State, Integer> dist = new HashMap<>();
[Link](start);
[Link](start, 0);

while (![Link]()) {
State cur = [Link]();
int d = [Link](cur);

if ([Link](goal)) return d;

for (int[] dir : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) {


State nxt = move(cur, dir[0], dir[1]);
if (nxt != null && ![Link](nxt)) {
[Link](nxt, d+1);
[Link](nxt);
}
}

for (State nxt : rotate(cur)) {


if (![Link](nxt)) {
[Link](nxt, d+1);
[Link](nxt);
}
}
}
return -1;
}

static State move(State s, int dr, int dc) {


if ([Link]) {
int r = s.r + dr;
int c = s.c + dc;
if (isFree(r, c) && isFree(r, c+1))
return new State(r, c, true);
} else {
int r = s.r + dr;
int c = s.c + dc;
if (isFree(r, c) && isFree(r+1, c))
return new State(r, c, false);
}
return null;
}

static List<State> rotate(State s) {


List<State> res = new ArrayList<>();
if ([Link]) {
int r = s.r, c = s.c;

if (r+1 < M && isFree(r, c) && isFree(r, c+1) && isFree(r+1, c) &&
isFree(r+1, c+1)) {
[Link](new State(r, c, false));
[Link](new State(r, c+1, false));
}
} else {
int r = s.r, c = s.c;
// rotate right
if (c+1 < N && isFree(r, c) && isFree(r+1, c) && isFree(r, c+1) &&
isFree(r+1, c+1)) {
[Link](new State(r, c, true));
[Link](new State(r+1, c, true));
}
}
return res;
}

static boolean isFree(int r, int c) {


if (r < 0 || r >= M || c < 0 || c >= N) return false;
return grid[r][c] != 'H';
}
}

You might also like