UVa 11906

From Algorithmist
Jump to navigation Jump to search

11906 - Knight in War Grid[edit]

Summary[edit]

Given a grid as large as 100 x 100 which has some squares with water, and a knight who can move M squares horizontally and N squares vertically, or M squares vertically and N squares horizontally in a single move (0 <= M, N <= 100, M + N > 0), count the number of odd and even marked squares that the knight can reach if he starts from square (0,0). An odd (even) marked square is a square reachable from (0,0) and has odd (even) number of squares that the knight can reach in one move.

Explanation[edit]

Run DFS on the grid.

Gotchas[edit]

  • Take care of the case where either M or N is 0, or when M = N. There are only 4 possible movements (compared to 8) for these cases.

Solutions[edit]

Input[edit]

2
3 3 2 1
0
4 4 1 2
2
3 3
1 1

Output[edit]

Case 1: 8 0
Case 2: 4 10

Categories here, use the form [[Category:UVa Online Judge|11906]] [[Category: Category Name]], see Categories for a list