C++ ] leetCode 2596 - Check Knight Tour Configuration

 

 

 

리트코드 2596번 문제

 

There is a knight on an n x n chessboard. In a valid configuration, the knight starts at the top-left cell of the board and visits every cell on the board exactly once.

 

You are given an n x 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 below illustrates all the possible eight moves of a knight from some cell.

 

 

 

 

 

 

 

 

Example 1: 

 

• Input: 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]]
• Output: true
• Explanation: The above diagram represents the grid. It can be shown that it is a valid configuration. 

 

 

Example 2:

• Input: grid = [[0,3,6],[5,8,1],[2,7,4]]
• Output: false
• Explanation: The above diagram represents the grid. The 8th move of the knight is not valid considering its position after the 7th move.

 

 

Constraints:

• n == grid.length == grid[i].length
• 3 <= n <= 7
• 0 <= grid[row][col] < n * n
• All integers in grid are unique.

 

 

재밌는 문제이다. 정사각형 체스판에서 나이트는 우측상단 셀에서 시작해서 모든 셀을 한번씩 밟으며 이동하는데 나이트는 L자 모양으로 움직일 수 있다. 수직2칸 수평1칸 움직이거나 수직1칸 수평2칸 움직일 수 있는데 나이트의 모든 이동이 valid한지 체크하여 true/false로 리턴하면 된다.

 

먼저 모든 셀을 순회하면서 이동 순서에 따른 좌표 위치를 matrix 벡터에 저장해두고 다시한번 matrix 벡터를 순회하면서 다음 셀로의 이동이 나이트 말의 이동규칙을 만족하는 검사하면 된다.

 

 

class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        if(grid[0][0] != 0) return false;

        int n = grid.size();        
        vector<pair<int, int>> matrix(n*n);

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                matrix[grid[i][j]] = make_pair(i, j);
            }
        }

        for(int i = 0; i < n*n - 1; i++) {
            int diffCol = abs(matrix[i].first - matrix[i + 1].first);
            int diffRow = abs(matrix[i].second - matrix[i + 1].second);
            if(!(diffCol == 2 && diffRow == 1) && !(diffCol == 1 && diffRow == 2)) {
                return false;
            }
        }

        return true;
    }
};