6) (15 pts) Graphs Breadth First Search

Consider the problem of attempting to get from the top left corner to the bottom right corner of a square grid in the minimum number of moves where each square is marked as '.' (valid) or 'X' (invalid). (Both the top left and bottom right corners are always guaranteed to be valid squares.) The valid moves are up, down, left and right and the top left corner is coordinate (0, 0) and the bottom right coordinate is (n-1, n-1), where n is given in the input. Complete the code below to correctly solve the problem. All of the I/O is handled and you just have to fill in portions of the method that conducts the breadth first search. (Note: The method is designed only to return the shortest distance to the bottom right corner, not to necessarily mark all of the shortest distances from the top left to all other squares.) The method returns -1 if there is no valid path.

import java.util.*; public class bfs_maze { 

 public static int n; public static char[][] grid; final public static int[] DX = {-1,0,0,1}; final public static int[] DY = {0,-1,1,0}; 

public static void main(String[] args) { Scanner stdin = new Scanner(System.in); int nC = stdin.nextInt(); 

for (int loop=0; loop

grid[i] = stdin.next().toCharArray(); System.out.println(bfs(0, n*n-1));

} }

 public static int bfs(int start, int end) { 

LinkedList q = new LinkedList(); int[][] dist = new int[n][n]; for (int i=0; i

 Arrays.fill(dist[i], -1); dist[start/n][start%n] = 0; q.offer(start); 

while (q.size() > 0) { int cur = q.poll(); if (cur == _____ ) return dist[ ______ ][ ______ ];

 for (int i=0; i 
 int x = ___________________; 
 
 int y = ___________________; 
 
if (!inbounds(x,y) || dist[x][y] != ___ || grid[x][y] == ___) continue;
 
 q.offer( ___________________ ); 
 
 dist[x][y] = dist[ ______ ][ ______ ] + 1; } 
 
}
 
return -1; }
 
public static boolean inbounds(int tryX, int tryY) { return tryX >= 0 && tryX < n && tryY >= 0 && tryY < n;
 
} }