题目描述
骑士在一张 n x n
的棋盘上巡视。在有效的巡视方案中,骑士会从棋盘的 左上角 出发,并且访问棋盘上的每个格子 恰好一次。
给你一个 n x n
的整数矩阵 grid
,由范围 [0, n * n - 1]
内的不同整数组成,其中 grid[row][col]
表示单元格 (row, col)
是骑士访问的第 grid[row][col]
个单元格。骑士的行动是从下标 0 开始的。
如果 grid
表示了骑士的有效巡视方案,返回 true
;否则返回 false
。
注意,骑士行动时可以垂直移动两个格子且水平移动一个格子,或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。
样例
输入:grid = [[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]]
输出:true
解释:grid 如上图所示,可以证明这是一个有效的巡视方案。
输入:grid = [[0,3,6],[5,8,1],[2,7,4]]
输出:false
解释:grid 如上图所示,考虑到骑士第 7 次行动后的位置,第 8 次行动是无效的。
限制
n == grid.length == grid[i].length
3 <= n <= 7
0 <= grid[row][col] < n * n
grid
中的所有整数 互不相同。
算法1
(预处理) $O(n^2)$
- 预处理 $grid$ 每个整数的下标对,然后按顺序遍历,判断相邻的下标对是否合法。
时间复杂度
- 遍历数组一次,按顺序遍历下边一次,故时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n^2)$ 的额外空间存储下标对。
C++ 代码
class Solution {
public:
bool checkValidGrid(vector<vector<int>>& grid) {
const int n = grid.size();
vector<int> vx(n * n), vy(n * n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
vx[grid[i][j]] = i;
vy[grid[i][j]] = j;
}
if (!(vx[0] == 0 && vy[0] == 0))
return false;
for (int i = 1; i < n * n; i++)
if (!((abs(vx[i] - vx[i - 1]) == 1 && abs(vy[i] - vy[i - 1]) == 2) ||
(abs(vx[i] - vx[i - 1]) == 2 && abs(vy[i] - vy[i - 1]) == 1)))
return false;
return true;
}
};
算法2
(模拟验证) $O(n^2)$
- 从 $(0, 0)$ 开始,每次寻找下一个合法的位置,判定其位置上的数字是否合法。
时间复杂度
- 最多遍历遍历数组一次,每次遍历最多访问 $8$ 个方向,故时间复杂度为 $O(n^2)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
bool checkValidGrid(vector<vector<int>>& grid) {
const int n = grid.size();
const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
if (grid[0][0] != 0)
return false;
int x = 0, y = 0;
for (int i = 1; i < n * n; i++) {
bool ok = false;
for (int d = 0; d < 8; d++) {
int tx = x + dx[d], ty = y + dy[d];
if (tx < 0 || tx >= n || ty < 0 || ty >= n)
continue;
if (grid[tx][ty] == i) {
ok = true;
x = tx; y = ty;
break;
}
}
if (!ok)
return false;
}
return true;
}
};