Every day a Leetcode
题目来源：2596. 检查骑士巡视方案
解法1：广度优先搜索
这是有点特殊的广度优先搜索，每个位置需要搜索 8 个方向，但最终只选择其中的一个方向走下去。
所以不需要使用队列，也不需要标记数组，来保存某个位置是否被访问过，只需要用两个变量 (x, y) 来表示当前位置即可。
代码：
/** @lc app=leetcode.cn id=2596 lang=cpp** [2596] 检查骑士巡视方案*/// @lc code=start
class Solution
{
private:const int dx[8] = {-2, -2, -1, -1, 2, 2, 1, 1};const int dy[8] = {-1, 1, -2, 2, -1, 1, -2, 2};public:bool checkValidGrid(vector<vector<int>> &grid){// 特判if (grid[0][0] != 0)return false;int n = grid.size();// 骑士会从棋盘的左上角出发int x = 0, y = 0;int index = 0, steps = n * n;for (index = 1; index < steps; index++){bool flag = false;for (int i = 0; i < 8; i++){int r = x + dx[i], c = y + dy[i];if (r >= 0 && r < n && c >= 0 && c < n && grid[r][c] == index){x = r, y = c;flag = true;break;}}if (flag == false)return false;}return true;}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(n2)，其中 n 是数组 grid 的长度。
空间复杂度：O(1)。
解法2：模拟
依次检测每一次跳跃的行动路径是否为「日」字形。
代码：
// 模拟class Solution
{
public:bool checkValidGrid(vector<vector<int>> &grid){if (grid[0][0] != 0){return false;}int n = grid.size();vector<array<int, 2>> indices(n * n);for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)indices[grid[i][j]] = {i, j};for (int i = 1; i < indices.size(); i++){int dx = abs(indices[i][0] - indices[i - 1][0]);int dy = abs(indices[i][1] - indices[i - 1][1]);if (dx * dy != 2)return false;}return true;}
};
结果：
复杂度分析：
时间复杂度：O(n2)，其中 n 是数组 grid 的长度。
空间复杂度：O(n2)，其中 n 是数组 grid 的长度。
