Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.LinkedList;
- import java.util.Scanner;
- import javafx.util.Pair;
- public class Test3
- {
- public static void main(String[] args)
- {
- Scanner s = new Scanner(System.in);
- int[][] maze = new int[10][5];
- int startX = 0, startY = 0;
- for (int i = 0; i < 5; i++)
- {
- for (int j = 0; j < 10; j++)
- {
- if (s.hasNextInt())
- maze[j][i] = s.nextInt();
- else
- {
- if (s.next().equalsIgnoreCase("S"))
- {
- maze[j][i] = 2;
- startX = j;
- startY = i;
- }
- else
- if (s.next().equalsIgnoreCase("E"))
- maze[j][i] = -1;
- }
- }
- }
- System.out.println("The shortest path to the exit: " + bfs(maze, new Pair<>(startX, startY)));
- }
- public static int bfs(int[][] maze, Pair<Integer, Integer> start)
- {
- boolean[][] visited = new boolean[10][5];
- int[][] distance = new int[10][5];
- LinkedList<Pair<Integer, Integer>> queue = new LinkedList<>();
- // Where the maze starts
- queue.add(start);
- distance[start.getKey()][start.getValue()] = 0;
- visited[start.getKey()][start.getValue()] = true;
- while (!queue.isEmpty())
- {
- Pair<Integer, Integer> p = queue.poll();
- int x = p.getKey(), y = p.getValue();
- // find neighbors
- for (int i = -1; i <= 1; i += 2)
- {
- // valid neighbors
- if (x + i < 0 || y < 0 || x + i >= 10 || y >= 5 || maze[x + i][y] == 1)
- continue;
- else
- if (maze[x + i][y] == -1)
- return distance[x][y] + 1;
- else
- if (!visited[x + i][y])
- {
- visited[x + i][y] = true;
- distance[x + i][y] = distance[x][y] + 1;
- queue.push(new Pair<>(x + i, y));
- }
- }
- for (int j = -1; j <= 1; j++)
- {
- // valid neighbors
- if (x < 0 || y + j < 0 || x >= 10 || y + j >= 5 || maze[x][y + j] == 1)
- continue;
- else
- if (maze[x][y + j] == -1)
- return distance[x][y] + 1;
- else
- if (!visited[x][y + j])
- {
- visited[x][y + j] = true;
- distance[x][y + j] = distance[x][y] + 1;
- queue.push(new Pair<>(x, y + j));
- }
- }
- }
- return 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement