Need to create solveBFS$()$ method $($use queue$)$ & test it$.$ Given:

import java.io$.$BufferedReader;

import java.io$.$FileReader;

import java.io$.$FileWriter;

import java.io$.$IOException;

import java.io$.$PrintWriter;

import java.util.Stack;

import java.util.LinkedList;

import java.util.Queue;

import java.util.ArrayList;

public class Pacman $\{$

private Node$[][]$ maze;

private String inputFileName;

private String outputFileName;

private int height;

private int width;

private int startX;

private int startY;

private static class Node $\{$

private char content;

private int row;

private int col;

private boolean visited;

private Node parent;

public Node$($int x$,$ int y$,$ char c$)\{$

visited $=$ false;

content $=$ c;

parent $=$ null;

this.row $=$ x;

this.col $=$ y;

$\}$

public boolean isWall$()\{$ return content $==\text{'}$X$\text{'}$; $\}$

public boolean isVisited$()\{$ return visited; $\}$

$\}$

public Pacman$($String inputFileName, String outputFileName$)\{$

this.inputFileName $=$ inputFileName;

this.outputFileName $=$ outputFileName;

buildGraph$()$;

$\}$

private boolean inMaze$($int index, int bound$)\{$

return index $<$ bound && index $>=0$;

$\}$

private void backtrack$($Node end$)\{$

Node current $=$ end;

while $($current $!=$ null$)\{$

if $($current$.$content $!=\text{'}$S$\text{'}$ && current.content $!=\text{'}$G$\text{'})\{$

current.content $=\text{'}.\text{'}$;

$\}$

current $=$ current.parent;

$\}$

$\}$

public void writeOutput$()\{$

try $\{$

PrintWriter output $=$ new PrintWriter$($new FileWriter$($outputFileName$))$;

output.println$($height $+""+$ width$)$;

for $($int i $=0$; i $<$ height; i$++)\{$

StringBuilder line $=$ new StringBuilder$()$;

for $($int j $=0$; j $<$ width; j$++)\{$

char content $=$ maze$[$i$][$j$].$content;

if $($content $==\text{'}\text{'})\{$

line.append$(\text{'}.\text{'})$;

$\}$ else $\{$

line.append$($content$)$;

$\}$

$\}$

output.println$($line$.$toString$())$;

$\}$

output.close$()$;

$\}$ catch$($IOException e$)\{$

e$.$printStackTrace$()$;

$\}$

$\}$

public String toString$()\{$

String s $=""$;

s $+=$ height $+""+$ width $+"$

$"$;

for $($int i $=0$; i $<$ height; i$++)\{$

for $($int j $=0$; j $<$ width; j$++)\{$

s $+=$ maze$[$i$][$j$].$content $+""$;

$\}$

s $+="$

$"$;

$\}$

return s;

$\}$

private void buildGraph$()\{$

try $\{$

BufferedReader input $=$ new BufferedReader$($new FileReader$($inputFileName$))$;

int i $=0$;

int j $=0$;

String input$\_$str $=$ input.readLine$()$;

String $[]$ str$\_$array $=$ input$\_$str$.$split$("")$;

height $=$ Integer.parseInt$(($str$\_$array$[0]))$;

width $=$ Integer.parseInt$(($str$\_$array$[1]))$;

maze $=$ new Node$[$height$][$width$]$;

for $($i$=0$; i $<$ height; i$++)\{$

input$\_$str $=$ input.readLine$()$;

for $($j $=0$; j $<$ width; j$++)\{$

maze$[$i$][$j$]=$ new Node$($i$,$ j$,$ input$\_$str$.$charAt$($j$))$;

if $($input$\_$str$.$charAt$($j$)==\text{'}$S$\text{'})\{$

startX $=$ i;

startY $=$ j;

$\}$

$\}$

$\}$

input.close$()$;

$\}$ catch $($IOException e$)\{$

e$.$printStackTrace$()$;

$\}$

$\}$

public ArrayList getNeighbors$($Node currentNode$)\{$

Node north, south, east, west;

ArrayList nbors $=$ new ArrayList$<>()$;

int row $=$ currentNode.row;

int col $=$ currentNode.col;

north $=$ maze$[$row $-1][$col$]$;

south $=$ maze$[$row $+1][$col$]$;

west $=$ maze$[$row$][$col $-1]$;

east $=$ maze$[$row$][$col $+1]$;

if $($inMaze$($row $-1,$ height$)$ &&

$!$north.isWall$()$ &&

$!$north.isVisited$())\{$

nbors.add$($north$)$;$\}$

if $($inMaze$($row $+1,$ height$)$ &&

$!$south.isWall$()$ &&

$!$south.isVisited$())\{$

nbors.add$($south$)$;$\}$

if $($inMaze$($col $-1,$ width$)$ &&

$!$west.isWall$()$ &&

$!$west.isVisited$())\{$

nbors.add$($west$)$;$\}$

if $($inMaze$($col $+1,$ width$)$ &&

$!$east.isWall$()$ &&

$!$east.isVisited$())\{$

nbors.add$($east$)$;$\}$

return nbors;

$\}$

$\}$