[UVA] 11906 - Knight in a War Grid
|
H |
Knight in War Grid |
Once upon an ancient time, a knight was preparing for the great battle in GridLand. The GridLand is divided into square grids. There are R horizontal and C vertical grids. Our particular knight in this case can always give an (M, N) move, i.e. he can move M squares horizontally and N squares vertically or he can move M squares vertically and N squares horizontally in a single move. In other words he can jump from square (a, b) to square (c, d) if and only if, either (|a - c| = M and |b - d| = N) or (|a - c| = N and |b - d| = M). However, some of the squares in the war field are filled with water. For a successful jump from one square to another, none of the squares should contain water. Now, the knight wants to have a tour in the war field to check if everything is alright or not. He will do the following:
a) He will start and end his tour in square (0, 0) but visit as many squares as he can.
b) For each square si, he counts the number ki of distinct squares, from which he can reach si in one jump (satisfying the jumping condition). Then he marks the square as an even square if ki is even or marks it odd if ki is odd. The squares he cannot visit remain unmarked.
c) After coming back to square (0, 0) he counts the number of even and odd marked squares. He can visit a square more than once.
You, as an advisor of the knight, suggested that, he can do it without visiting all the squares, just by writing a program. So the knight told you to do so. He will check your result at the end of his visit.
Input
The first line of input will contain T (≤ 50) denoting the number of cases.
Each case starts with four integers R, C, M, N (1 < R, C ≤ 100, 0 ≤ M, N ≤ 50, M + N > 0). Next line contains an integer W (0 ≤ W < R * C), which is the number of distinct grids containing water. Each of the next W lines contains a pair of integer xi, yi (0 ≤ xi < R, 0 ≤ yi < C, xi + yi > 0).
Output
For each case, print the case number and the number of even and odd marked squares.
Sample Input |
Output for Sample Input |
|
2 3 3 2 1 0 4 4 1 2 2 3 3 1 1 |
Case 1: 8 0 Case 2: 4 10 |
Problem Setter: Md. Towhidul Islam Talukder, Special Thanks: Jane Alam Jan
從 (0,0) 出發，然後位移量是 (±M, ±N) or (±N, ±M) 總共 8 種，
ki 的計算是該點如果可以從 (0,0) 到達，那麼這點可已經藉由上方 8 種情況到達多少個不同的點。
這別要特別小心 M == N，以及盤面上只有 (0,0) 這點的處理。
#include <stdio.h>
#include <queue>
#include <set>
using namespace std;
int main() {
int testcase, cases = 0;
int R, C, M, N, W;
int x, y, tx, ty;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d %d", &R, &C, &M, &N);
scanf("%d", &W);
int g[105][105] = {}, s[105][105] = {};
int dx[8] = {M,M,-M,-M,N,N,-N,-N};
int dy[8] = {N,-N,N,-N,M,-M,M,-M};
while(W--) {
scanf("%d %d", &x, &y);
g[x][y] = 1;
}
queue<int> X, Y;
X.push(0), Y.push(0);
g[0][0] = -1;
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
int ki = 0;
set<pair<int, int> > S;
for(i = 0; i < 8; i++) {
tx = x+dx[i], ty = y+dy[i];
if(tx < 0 || ty < 0 || tx >= R || ty >= C)
continue;
if(g[tx][ty] != 1 && S.find(make_pair(tx, ty)) == S.end()) {
ki++;
S.insert(make_pair(tx, ty));
}
if(g[tx][ty] == 0) {
g[tx][ty] = -1;
X.push(tx);
Y.push(ty);
}
}
s[x][y] = ki;
}
int odd = 0, even = 0;
if(s[0][0] == 0)
s[0][0] = 2;
for(i = 0; i < R; i++) {
for(j = 0; j < C; j++) {
if(s[i][j]) {
if(s[i][j]&1)
odd++;
else
even++;
}
}
}
printf("Case %d: %d %d\n", ++cases, even, odd);
}
return 0;
}