# UVa 11906

Jump to navigation
Jump to search

## Contents

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