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

# 題目說明

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


INPUT:
第一行有一個整數 T ,代表有 T 筆測資
每筆測資第一行有四個整數 RCMN

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

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


OUTPUT:
輸出 evenodd 的數量

# 解題方法

dfs ,紀錄每個點被走到的次數
最後再計算 evenodd 的數量

n 儲存 8 種移動法

  1. 如果 MN 其中一項為 0 ,則只需要移動前 4 種
  2. 如果 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/