aboutsummaryrefslogtreecommitdiff
path: root/other/check_knight_config.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/check_knight_config.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/check_knight_config.cpp')
-rw-r--r--other/check_knight_config.cpp59
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
+}