1 条题解

  • 0
    @ 2025-4-29 13:15:07
    
    
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    
    bool isValid(int x, int y, int n, int m, vector<vector<bool>>& visited) {
        return (x >= 0 && x < n && y >= 0 && y < m && !visited[x][y]);
    }
    
    void knightTour(int x, int y, int moveCount, int n, int m, vector<vector<bool>>& visited, int& count) {
        if (moveCount == n * m) {
            count++;
            return;
        }
    
        visited[x][y] = true;
    
        for (int k = 0; k < 8; ++k) {
            int newX = x + dx[k];
            int newY = y + dy[k];
    
            if (isValid(newX, newY, n, m, visited)) {
                knightTour(newX, newY, moveCount + 1, n, m, visited, count);
            }
        }
    
        visited[x][y] = false;
    }
    
    int main() {
        int T;
        cin >> T;
    
        while (T--) {
            int n, m, startX, startY;
            cin >> n >> m >> startX >> startY;
    
            vector<vector<bool>> visited(n, vector<bool>(m, false));
            int count = 0;
    
            knightTour(startX, startY, 1, n, m, visited, count);
    
            cout << count << endl;
        }
    
        return 0;
    }
    
    
    
    
    • 1

    信息

    ID
    700
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    (无)
    递交数
    3
    已通过
    2
    上传者