Nộp bài  Các bài nộp  Làm tốt nhất  Về danh sách bài 
MGAME1  Game 
English  Vietnamese 
Note: C, S, B are used instead of H, F, I, respectively, in test case.
Hal and Dave are playing an interesting game on a rectangular chesslike board consisting of squares arranged in R rows and C columns. Here are the rules of the game:
 There is only one piece on a board alternately moved by the players.
 One move of the piece consists of moving it to an adjacent square in one of following directions: down, right or diagonally right–down.
 Some squares on a board are ‘forbidden’, i.e. the piece cannot enter such squares.
 A square may contain at most one of the following: a hamburger, french fries, ice cream. A player who moves the piece to a square with a hamburger receives 1 point, with french fries 3 points and with ice cream 5 points.
 The game ends when a player who should make a move cannot make it (because piece would fall off of board or enter a forbidden square in all three directions).
 If at the end of a game both players have same number of points, then the one who cannot make a legal move lost that game.
 If at the end of a game players have different numbers of points, then the player with more points won the game.
 Both players have 0 points at the beginning of a game. Hal makes first move. The initial position of the piece is a square that is not forbidden and it does not contain any food.
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.
Input
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 top to bottom with number from 1 to R, and columns are numbered from left to right with numbers from 1 to C.
Output
Output file should contain N lines. The i^{th} line should contain name of a player (i.e. DAVE or HAL) having a winning strategy for i^{th} given initial position.
Sample
Input: 3 4 .H#. I... ##H. 3 1 1 1 4 2 3 Output: HAL DAVE HAL
Input: 4 5 .#... #.#.F .#..F .#... 3 3 1 3 3 1 5 Output: HAL HAL HAL
Input: 5 6 ##..#. ..#FH# ..#..# ###... .....I 4 2 1 5 1 1 4 1 6 Output: HAL HAL DAVE DAVE
Được gửi lên bởi:  psetter 
Ngày:  20090313 
Thời gian chạy:  0.100s 
Giới hạn mã nguồn:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Ngôn ngữ cho phép:  Tất cả ngoại trừ: ERL GOSU JSRHINO NODEJS PERL6 PYPY RUST SED VB.NET 
Nguồn bài:  COI 01 
hide comments
20121028 15:54:44 1212
Cho em hỏi "xuống dưới và sang phải" nghĩa là "xuống dưới rồi mới sang phải" hay làm cái nào trước cũng dc? 

20090314 06:56:38 Nguyễn Quang Anh
de bai la cac ky tu H,F,I nhung Input la C,S,B 