시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 5 | 3 | 2 | 50.000% |
Hal and Dave are playing an interesting game on a rectangular chess like board consisting of squares arranged in R rows and C columns. Here are the rules of the game:
Since there is a finite number of sequence of moves finishing any given game, it can be proved that for any given initial position of the piece either Dave or Hal can win no matter how the other player plays, i.e. he has a winning strategy.
A board, positions of forbidden squares, positions of squares with food and some initial positions are given. Write a program that will determine for each given initial position which player has a winning strategy.
The first line of input file contains two integers R, number of rows (2 ≤ R ≤ 100) and C, number of columns (2 ≤ C ≤ 100) of a board, separated by a space character.
Each of next R lines contains a sequence of C characters representing a corresponding row of the board. Forbidden squares are represented with ‘#’ character. Squares containing food are represented with letters H (hamburger), F (french fries) and I (ice cream). Other squares are represented with a dot character (‘.’).
The next line contains an integer N, 1 ≤ N ≤ 100, the number of given initial positions for which a program should find which player has a winning strategy.
Each of the following N lines contain two integers A (1 ≤ A ≤ R) and B (1 ≤ B ≤ C), separated with a space character, which determine a row and a column of an initial position of a piece.
Rows are numbered from up to down with number from 1 to R, and columns are numbered from left to right with numbers from 1 to C.
Output file should contain N lines. The ith line should contain name of a player (i.e. DAVE or HAL) having a winning strategy for ith given initial position.
3 4 .H#. I… ##H. 3 1 1 1 4 2 3
HAL DAVE HAL
4 5 .#... #.#.F .#..F .#... 3 3 1 3 3 1 5
HAL HAL HAL
5 6 ##..#. ..#FH# ..#..# ###... .....I 4 2 1 5 1 1 4 1 6
HAL HAL DAVE DAVE