Discrete Mathematics

Suppose some squares in an nxn chess board are marked blocked. The following figure shows an example. Let (i.j) be the square at row i and column j, 1Si.jsn. B(i, j) 0 If square (i, j) is blocked, otherwise B(i, j)-1. We assume squares (1. 1) and (1. n) are unblocked. You can move from a square to an adjacent square if the adjacent square is unblocked. Please design an O( algorithm to find a shortest moving path from square (1, 1) to square (1, n). The number of squares, including (1, 1) and (1, n) you have passed is the length of your path. Report d o if no such a path exists. The following figure also shows the shortest path for the 8x8 chessboard Suppose some squares in an nxn chess board are marked blocked. The following figure shows an example. Let (i.j) be the square at row i and column j, 1Si.jsn. B(i, j) 0 If square (i, j) is blocked, otherwise B(i, j)-1. We assume squares (1. 1) and (1. n) are unblocked. You can move from a square to an adjacent square if the adjacent square is unblocked. Please design an O( algorithm to find a shortest moving path from square (1, 1) to square (1, n). The number of squares, including (1, 1) and (1, n) you have passed is the length of your path. Report d o if no such a path exists. The following figure also shows the shortest path for the 8x8 chessboard