Leetcode2596. 检查骑士巡视方案

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(n²)，其中 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;
    }
};