Problem Statement
You are given a 8x8 chessboard containing a knight. A knight moves two cells in one of four directions (up, down, left or right), and then one more cell in a perpendicular direction. It must always remain on the chessboard. Some of the cells on the chessboard are occupied, and the knight is not allowed to land in any of those cells. The knight is initially standing on a free cell.
8 .N...... 7 ........ 6 ........ 5 ........ 4 ..xxx... 3 ..x.x... 2 ..xxx... 1 ........ abcdefgh
The 'N' character represents the knight, 'x' characters represent occupied cells, and '.' characters represent free cells. In the example above, cell d3 can be visited in 3 moves.
You are given a String[] chessboard containing the initial layout of the board. Element 0 of chessboard contains cells a8, b8, c8, ..., h8; element 1 contains cells a7, b7, c7, ..., h7; and so on. You are also given a String[] queries. Each element of queries is formatted as "cr K" (quotes for clarity), where c and r are the column and row, respectively, of a cell, and K is an integer. Columns are labelled 'a' to 'h' (left to right) and rows are numbered '1' to '8' (bottom to top). Each element of queries represents a single question: Can the knight reach the cell at column c, row r in exactly K moves from its initial starting position? Note that the knight is allowed to revisit free cells (including its starting and destination cells) multiple times. Return a String that contains exactly n characters, where n is the number of elements in queries. The i-th character of the return value should be 'Y' if the answer to the i-th element of queries is yes, and 'N' otherwise.
Definition
- Class:
- KnightAttack
- Method:
- isReachable
- Parameters:
- String[], String[]
- Returns:
- String
- Method signature:
- String isReachable(String[] chessboard, String[] queries)
- (be sure your method is public)
Constraints
- chessboard will contain exactly 8 elements and each element will contain exactly 8 characters.
- Each element of chessboard will contain only 'N', '.' or 'x' characters.
- There is exactly one 'N' character in chessboard.
- queries will have contain between 1 and 50 elements, inclusive.
- Each element of queries will be formatted as "cr K" (quotes for clarity), where c is a lowercase letter between 'a' and 'h', inclusive, r is a digit between '1' and '8', inclusive, and K is an integer between 1 and 1000000000, inclusive, with no leading zeroes.
- Each queried cell will be free.
Examples
{"........", ".N......", "........", "........", "........", "........", "........", "........"}{"a5 1", "c5 1", "d6 1", "d8 1"}Returns: "YYYY"
In the diagram below the queried cells are marked by asterisks. Each of them is reachable in one step. ...*.... .N...... ...*.... *.*..... ........ ........ ........ ........{"...x....", ".N......", "...x....", "..x.....", "..xx....", "....xx..", "...x....", "..x....."}{"a5 1", "b3 2", "a1 3", "c2 4", "e1 5", "g2 6"}Returns: "YYYYYY"
In the diagram below the numbers 1 to 6 show one valid path of the knight. This path reaches each of the queried cells in the correct number of steps. ...x.... .N...... ...x.... 1.x..... ..xx.... .2..xx.. ..4x..6. 3.x.5...{".x.xx..x", ".x.x.xx.", "xx..xx..", "x.x.xx..", ".x.xx...", "x..N..xx", "xx....xx", "x.xx...."}{"b3 24", "e2 42", "e2 13", "d5 475", "g6 60", "h5 445", "f1 404", "a4 535", "e2 748", "g5 844", "d5 683", "g6 467", "h1 755", "h7 932", "c7 81", "c6 616", "h1 706", "e2 449", "c2 109", "g1 456", "b1 533", "b3 921", "b1 65", "e2 235", "b1 635", "c7 713", "d2 351", "a4 933", "d6 854", "a8 394", "g8 603", "e3 534", "h4 265", "e3 416", "a7 638", "e2 611", "f3 770", "e3 102", "e2 205", "f3 221", "c7 515", "c4 951", "b5 557", "c3 114", "c6 110", "f2 254", "h7 830", "c8 257", "c2 673", "b3 16"}Returns: "YYNNYNYNYNNNNYYYYNNNNNNNNYYNNYNNYNNNYNNNYNNNYNYNNY"
{"xxxxxxxx", "xxxxxxxx", "xxNxxxxx", "xxxxxxxx", "xxxxxxxx", "xxxxxxx.", "xxxxxxxx", ".xxxxxxx"}{"a1 33333", "h3 12222"}Returns: "NN"
The knight can not move at all.
Back to all problems