題目： UVa - 11906 - Knight in a War Grid

題目說明

有一個騎士在一個 R x C 的棋盤上移動，從 (0, 0) 開始，每次可以從該點移動到 (±M, ±N) 及 (±N, ±M) 的點，有些點有水則不能跳。如果一個點能從偶數個點跳過來則標記為 偶，如果能從奇數個點跳過來則標記為 奇。求整個棋盤上 奇 跟 偶 的個數。

Input： 第一行為一整數 T，代表有 T 組測資，每組測資的第一行為 4 個整數 R、C、M、N，接下來一行為一個整數 W，代表有 W 個有水的點，接下來 W 行，每行有兩個整數，代表有水的點的座標 **(x, y)**。

Output： 輸出每組測資的 偶、奇 個數。

解題思路

使用 DFS 模擬，紀錄每個點被走到的次數，最後再計算 奇、偶 的個數即可，需要注意的是若 M、N 皆大於 0 且不相同，每次會有 8 個點可以走，若 M、N 相同或是兩者中有一個為 0 則每次只會有 4 個點可以走。還有若是 (0, 0) 除了一開始走到之外都沒有被走到的話會被歸類在 even 裡面。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

#define LOOP(n) for(int I = 0; I < n; ++I)

using namespace std;

// reference: https://ppt.cc/f7N4Ix

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int main()
{
    int T, Case = 0;
    cin >> T;

    LOOP(T)
    {
        int R, C, M, N, W;
        cin >> R >> C >> M >> N >> W;

        // 0 沒走過，>= 1 走過，-1 有水 ( 不能走 )
        vector<vector<int>> maps(R, vector<int>(C));

        LOOP(W)
        {
            int x, y;
            cin >> x >> y;
            maps[x][y] = -1;
        }

        function<void(int, int)> dfs = [&](int x, int y)
        {
            if (x < 0 || x >= R || y < 0 || y >= C || maps[x][y] == -1) return;

            // 如果當前的點已經有往下走過的話就只要增加可以走到當前的點的次數即可
            if (maps[x][y]++ != 0) return;

            int _x = M, _y = N;
            LOOP(2)
            {
                dfs(x + _x, y + _y);
                dfs(x - _x, y - _y);
                if (_x && _y)
                {
                    dfs(x + _x, y - _y);
                    dfs(x - _x, y + _y);
                }
                if (_x == _y) break;
                swap(_x, _y);
            }
        };

        dfs(0, 0);
        --maps[0][0];

        int odd = 0, even = 0;
        for (auto& v : maps) for (auto& i : v)
        {
            if (i <= 0) continue;
            i & 1 ? ++odd : ++even;
        }

        // 若 (0, 0) 只有在一開始的時候走到過，代表為 even
        if (!maps[0][0]) ++even;

        cout << "Case " << ++Case << ": " << even << ' ' << odd << '\n';
    }
}

參考資料

UVa 11906 - Knight in a War Grid