# 題目: UVa 11906 - Knight in a War Grid
# 題目說明
有一個騎士在 R*C
的棋盤上移動,每次移動 (±M, ±N)
及 (±N, ±M)
格,有水則不能移動
若一個點能從偶數個點移動過來,則標記為 even
若一個點能從奇數個點移動過來,則標記為 odd
求 even
及 odd
的數量
INPUT:
第一行有一個整數 T
,代表有 T
筆測資
每筆測資第一行有四個整數 R
、 C
、 M
、 N
R
代表有幾行C
代表有幾列M
和N
代表每次移動的距離,(±M, ±N)
及(±N, ±M)
第二行有一個整數 W
,代表有水的格子的數量
接下來有 W
行,代表有水的格子的座標
OUTPUT:
輸出 even
及 odd
的數量
# 解題方法
跑 dfs
,紀錄每個點被走到的次數
最後再計算 even
及 odd
的數量
以 n
儲存 8 種移動法
- 如果
M
與N
其中一項為0
,則只需要移動前 4 種 - 如果
M = N
,則只需要移動前兩種及後兩種
將有水的格子設為 -1
# 參考程式碼
#include <iostream> | |
#include <vector> | |
using namespace std; | |
vector< vector<int> > square; | |
vector< pair<int, int> > n; | |
int R, C, M, N, W; | |
void dfs(int x, int y) | |
{ | |
if (square[x][y]++ != 0) return; | |
for (int i = 0, nx, ny; i < 8; ++i) { | |
nx = x + n[i].first; | |
ny = y + n[i].second; | |
if (nx >= 0 && ny >= 0 && nx < R && ny < C && square[nx][ny] != -1) dfs(nx, ny); | |
if (i == 3 && (!n[i].first || !n[i].second)) break; | |
if (i == 1 && n[i].first == n[i].second) i += 4; | |
} | |
} | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int T, Case = 0; | |
cin >> T; | |
while (T--) { | |
cin >> R >> C >> M >> N >> W; | |
square.clear(); | |
square.assign(R, vector<int>(C)); | |
n.clear(); | |
n.emplace_back(make_pair(M, N)); | |
n.emplace_back(make_pair(-M, -N)); | |
n.emplace_back(make_pair(N, M)); | |
n.emplace_back(make_pair(-N, -M)); | |
n.emplace_back(make_pair(-N, M)); | |
n.emplace_back(make_pair(N, -M)); | |
n.emplace_back(make_pair(-M, N)); | |
n.emplace_back(make_pair(M, -N)); | |
while (W--) { | |
int a, b; | |
cin >> a >> b; | |
square[a][b] = -1; | |
} | |
dfs(0, 0); | |
++square[0][0]; | |
int odd = 0, even = 0; | |
for (auto& i : square) | |
for (auto& j : i) if (j > 0) j & 1 ? ++odd : ++even; | |
cout << "Case " << ++Case << ": " << even << " " << odd << "\n"; | |
} | |
return 0; | |
} |
# 參考資料
https://www.larrysprognotes.com/UVa%20-%2011906/