diff options
Diffstat (limited to 'other/check_knight_config.cpp')
-rw-r--r-- | other/check_knight_config.cpp | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/other/check_knight_config.cpp b/other/check_knight_config.cpp new file mode 100644 index 0000000..1d97495 --- /dev/null +++ b/other/check_knight_config.cpp @@ -0,0 +1,59 @@ +// 2596. Check Knight Tour Configuration +#include "leetcode.h" + +/* + * there is a knight on an 'n * n' chessboard. in a valid config + * the knight starts at the topl-left cell of the board and visits + * every cell on the board exactly once. you are given an 'n * n' + * integer matrix 'grid' consisting of distinct integers from the + * range '[0, n * n - 1]' where 'grid[row][col]' indicates that + * the cell '(row, col)' is the 'grid[row][col]'th cell that the + * knight visited. the moves are 0-indexed. return true if grid + * represents a valid configuration of the knight's movements or + * false otherwise. note that a valid knight move consists of + * moving two squares vertically and one square horizontally, + * or two squares horizontally and one square vertically. the + * figure illustrates all possible 8 moves of a knight from cell + */ + +class Solution { +public: + bool checkValidGrid(vvd & grid) { + int dir[8][2] = {{1, -2}, {2, -1}, {2, 1}, {1, 2}, + {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}}; + int cnt = 0, max_cnt = grid.size() * grid.size() - 1; + int x = 0, y = 0, i, j; + if (grid[x][y] != cnt) + return false; + while (cnt < max_cnt) { + cnt++; + int flag = 1; + for (auto d : dir) { + i = x + d[0]; + j = y + d[1]; + if (i >= 0 && j >= 0 && i < grid.size() && j < grid.size() && + grid[i][j] == cnt) { + x = i; + y = j; + flag = 0; + break; + } + } + if (flag) + return false; + } + return true; + } +}; + +int main() { + Solution obj; + vvd g1 = {{0, 11, 16, 5, 20}, + {17, 4, 19, 10, 15}, + {12, 1, 8, 21, 6}, + {3, 18, 23, 14, 9}, + {24, 13, 2, 7, 22}}; + vvd g2 = {{0, 3, 6}, {5, 8, 1}, {2, 7, 4}}; + printf("%d\n", obj.checkValidGrid(g1)); // expect: 1 + printf("%d\n", obj.checkValidGrid(g2)); // expect: 0 +} |