PUCMM335 - The Rook and The Rookette

Once upon a time, there was a noble rook called Danny who lived in a normal 8x8 chessboard. All squares lived in peace and Danny was a joyful rook, moving either vertically or horizontally across the board, never going off limits. Oh boy did he enjoy moving! He spent all days visiting the 64 squares and bringing flowers and other gifts to them. All squares loved Danny very much, even though they felt sorry for him because there was no Rookette for him to date.

The King took notice of the squares’ gossiping and he did something very remarkable. He arranged Danny a date with María, a Rookette from another chessboard. So, María stepped in one of the squares and Danny went immediately after her. However, the King made sure it wasn’t easy for Danny. He told him:

“Danny, I love you very much. We all do. What I am doing right now is because I love you.”

Danny was perplexed, without a clue. “What do you mean, Oh righteous King?”

Suddenly, the King arranged M bombs in M squares. “In life, you must work hard to achieve your dreams. I cannot just hand María over to you. You need to earn your right to date her.”

“Oookkkk…” said Danny, in a doubtful tone.

“I may also step in one of the squares. Go after her!”

And off went Danny. Assume Danny is very desperate to meet her, so he will try to get to her in the shortest possible way. The King  wants to prolong Danny’s path (maybe to have him think thoroughly about becoming a man). The King needs to decide where he will step in, he has N empty squares to choose from.

Write a program that outputs the length of the path should both Danny and the King act optimally. There will always be a path.

Input

There is a single test case per input file. The first 8 lines contain 8 characters each, and they represent the initial state of the chessboard. The lines are enumerated from 0 to 7 and so are the 8 characters of each line. The character at position (i, j)  can be one of the following:

  • ‘.’ : an empty square.
  • ‘#’ : a bomb.
  • ‘?’ : the princess.
  • '$' : Danny.

The following line contains N (0 <= N <= 10), representing the number of empty squares the King has to choose from. Then follow N lines. Each of these lines contain two integers Xi, Yi (0 <= Xi, Yi <= 7), the position of an empty square.

Output

Write a single line containing the length of the path Danny takes to reach María, if both Danny and the King act optimally.

Sample

Input
$......?
########
########
########
########
########
########
#######.
1
7 7

Output
7

Added by:Olson Ortiz
Date:2013-01-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET

hide comments
2019-12-10 01:56:51
Simes, the autist in me wants to concur, but having gotten past a few WAs I'd say the statement does a good job of explaining the constraints. Just remember, the king is acting out of love.

Last edit: 2019-12-11 01:32:51
2019-12-09 08:46:18 Simes
edit: answered my questions. Thanks for the push @NG.

So much remains unexplained...
A: no it doesn't.

1. What is the king's goal after he has stepped in? Is it to help Danny because he loves him? Or to hinder Danny?
A: RTFM "The King wants to prolong Danny’s path"

2. What does it mean to hinder anyway? Can the king block Danny entirely? Or since there is always a path from Danny to Maria, is the king's goal to maximise the length of that path?
A: as above.

3. Can the king move once he's stepped in, or is he static?
A: no

4. Can Maria move?
A: no

5. Why is there a princess on the map, and where is Maria the Rookette?
A: Maria the Rookette is of royal blood.



Last edit: 2019-12-11 06:54:43
2016-02-16 10:32:14 [Rampage] Blue.Mary
(1) Xi is the row number count from top and Yi is the column number count from left.
(2)Some (Xi, Yi) may contains '#' (by assertion in my program).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.