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

asteroids Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

asteroids.html

Problem Description

Darth Tater, known before as Jiahai the Potato, has been forming a plan to attack the Rainbow Catlands, where happy cats and rainbows live in harmony. After turning towards the dark side, Darth Tater has broken off all connections to his previous master, the wise master Rar. However, while planning his grand master scheme to eliminate Master Rar once and for all, he has encountered a serious problem. His imperial star destroyers have been unable to traverse the densely populated asteroid field seperating them and Rainbow Catlands. The hardworking and dead imperial engineers have been working to attach booster engines to the asteroids to move them out of the star destroyer's way.

The asteroids and star destroyers are located on a plane (the 2D one not the flying one), and have a width of 1, a length larger than 1, and a direction (vertical or horizontal). Due to the lack of imperial engineers (the good ones had been baked by Darth Tater), the booster engine on the asteroids and star destroyer can only propel the objects along a certain direction parallel to its length. For example, in the asteroid field below, the asteroid #1 in Fig. 1 can only move up or down. The star destroyer is represented by "X" and can be of any valid length.

Input

The first line of input will consist of two integers, the number of rows M and the number of columns N in the asteroid field.

The next line of input will consist of two integers, the goal row A and the goal column B The goal row and goal column do not include the border '@'s and start from 0.

The next M + 2 lines will consist of N + 2 characters, representing the asteroid field. The asteroid field is guaranteed to be surrounded by '@'s. Every distinct asteroid will be represented by a unique alphanumeric character.

Output

A single integer, the least amount of moves required to move the star destroyer to reach the goal row and goal column. There will always be a way for Darth Tater to succeed.

Limits

Subtask 1 (3 points): M ≤ 2

Subtask 2 (7 points): M ≤ 3

Subtask 3 (90 points): M ≤ 7, N ≤ 7

Sample Testcase 1

Input

6 6
2 5
@@@@@@@@
@[email protected]
@[email protected]
@[email protected]
@[email protected]
@[email protected]
@[email protected]
@@@@@@@@
Output
3

Explanation

It is possible to move the star destroyer to the desired row and column in 3 moves.

Firstly, move asteroid #2 leftwards. After moving asteroid #1 downwards, the star destroyer can reach row 2 and column 5 in the next move

rainbowcatlands.png

Tags

Graph Theory, A* Search

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1383s32MBMinimum
2783s32MBMinimum
390113s32MBMinimum
4013s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o asteroids -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.