# 題目: UVa 11906 - Knight in a War Grid

# 題目說明

有一個騎士在R*C的棋盤上移動，每次移動(±M, ±N)及(±N, ±M)格，有水則不能移動
若一個點能從偶數個點移動過來，則標記為even
若一個點能從奇數個點移動過來，則標記為odd
求even及odd的數量

---

INPUT:
第一行有一個整數T，代表有T筆測資
每筆測資第一行有四個整數R、C、M、N

1. R代表有幾行
2. C代表有幾列
3. M和N代表每次移動的距離，(±M, ±N)及(±N, ±M)

第二行有一個整數W，代表有水的格子的數量
接下來有W行，代表有水的格子的座標

---

OUTPUT:
輸出even及odd的數量

# 解題方法

跑dfs，紀錄每個點被走到的次數
最後再計算even及odd的數量

# 參考程式碼

#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/