This page is still under construction.

Parts of this page are still being built. What you see may change.

Robot Vacuum

Interview

Time limit1sMemory limit1024 MB

Summary
A robot slides in each commanded direction until a box stops it; count the distinct grid cells it visits, including the start.
Level

Medium5 of 10

Topics
Simulation, Implementation, Array, Brute force
Solved
No attempts yet

Problem

A robot vacuum cleans a grid-shaped warehouse where heavy boxes sit on some cells. The vacuum follows a sequence of commands: up ("^"), right (">"), down ("v"), left ("<"). When the robot receives a command, it moves as far as it can in that direction until a box blocks it. Every cell the robot vacuum occupies at any point is cleaned, including the cell it starts on. Given the layout of the warehouse, the robot's starting position, and a sequence of commands, determine how many distinct cells will have been cleaned when the sequence ends.

Input

  • The first line contains three integers: RR (3≤R≤20003 \le R \le 2000) and CC (3≤C≤20003 \le C \le 2000), the number of rows and columns of the grid-shaped warehouse, and NN (1≤N≤20001 \le N \le 2000), the length of the command sequence.
  • The second line contains a string of length NN consisting of "^", ">", "v", "<", the command sequence sent to the robot.
  • The following RR lines describe the grid-shaped warehouse. The ii-th of these lines contains CC characters describing the ii-th row. Each character is either a period "." if a cell is empty, a square "#" if the cell contains a box, or "O" if the cell is the robot's starting position. Exactly one cell is guaranteed to contain "O". In addition, every cell on the edge of the grid is guaranteed to be "#".

Output

Print a single integer: the number of distinct cells cleaned by the robot.

Examples4

  1. Example 1

    Input
    5 5 4
v>^v
#####
#O#.#
#...#
##..#
#####
    Expected output
    6

  2. Example 2

    Input
    6 7 7
>>^<v><
#######
#.#.#.#
#.....#
#.....#
##O..##
#######
    Expected output
    12

  3. Example 3

    Input
    3 12 3
<<<
############
#.#.....O.##
############
    Expected output
    6

  4. Example 4

    Input
    8 10 14
<v>^<v>v<^^><>
##########
#.#......#
#....#...#
##......O#
#........#
#..#.....#
#....#...#
##########
    Expected output
    33