oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

lazycat Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

lazycat.html

The map of a house is given by an n x n grid as shown below (for a 4 x 4 case):

BF
XXF
FXXF
S

The walls of the house are marked with 'X', food items are marked by 'F', and a single bed is marked by a 'B'. The cat begins at position 'S' (which can be anywhere within the grid and not just at the bottom left hand corner). The objective of this question is to find the smallest number of steps needed to reach the bed from the starting position 'S', while visiting all food items. The cat can only step up, down, left and right, and cannot enter squares marked with 'X'.

Input

Your program will read from standard input the following data. The first line specifies the grid size n, where 2 ≤ n ≤ 30. Each of the following n lines contains n characters, each of which characterizes the corresponding cell of the grid. The bed is marked with a 'B', the food items with 'F', the walls with 'X' and the empty squares with '0' (the digit zero). All letters are uppercase only. You can assume that there are at least one and at most 10 occurrences of 'F'.

Output

Your program must write one line to the standard output, containing the smallest number of steps required for reaching all food items and then go to bed. If there is no way for the cat to reach all food items and the bed, the output line contains the number -1 instead. The line is terminated by a newline character.

Sample Input

4
B0F0
XXF0
FXXF
S000

Sample Output

11

Tags

NOI 2009, Graph Theory, TSP, Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110061s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o lazycat -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.