Moving Ball

View as PDF

Submit solution


Points: 100
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

Moving Ball

Problem Statement

You are given an n \times m grid, each with a corresponding direction:

  • U - up
  • D - down
  • L - left
  • R - right

A ball is placed somewhere on the grid. Each second, the ball moves 1 place in the direction of its current cell.

What is the minimum number of cells you have to change, such that the ball will remain on the grid forever, no matter where the ball is initially placed?

Input

The first line contains integers n and m, which denote the dimensions of the grid.

The next n lines contains m characters. Where the j-th charcter on the i-th line represents the direction of cell (i, j).

Output

One line, containing an integer representing the total number of cells you need to change.

Constraints

For all test cases:

  • 2 \le n, m\le 200

Sample Test Cases

Example 1
Input
4 4
D U R R 
D L U L 
D D D D 
D U R L
Out
3
Example 2
Input
5 10
R L R U D R D L D R 
L L D L L D R D L D 
D R L L R D U R D D 
R U L U R L L L U L 
U U U D L D U L L D
Output
6

Python Template

n, m = map(int, input())
grid = [input().split() for _ in range(n)]

Comments

There are no comments at the moment.