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

flybot Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

flybot.html

Problem Description

Ranald the cat is coding a flybot today! The main objective of this flybot is to get from the top left hand corner of the wall to the bottom right hand corner. The flybot will be at the top left hand corner initially.

Walls are described using a grid system where each cell represents a centimetre square, where by '.' denotes a empty section of a wall and 'X' denotes an object (such as posters or pictures pinned to the wall). The flybot cannot pass through such objects.

The flybot can only move right since it is poorly coded, it also can only move downwards as it does not have enough power to overcome gravity.

Ranald the cat wonders how many different routes are there for his flybot to complete its objective. As this number can be very huge, he just needs to know the remainder of that number when divided by 1000000007.

It should be also noted that the top left hand corner and the bottom right hand corner of the wall will only be '.' and not 'X'.

Input

The first line of input contains H and W, which is the height and width of the wall in centimeteres respectively.

The following H lines of input will contain W characters each, either '.' or 'X'. These lines describe Ranald the cat's wall.

Output

A single integer, the remainder of the number of ways Ranald's flybot can complete its objective when divided by 1000000007.

Limits

Subtask 1 (30%): 0 < H, W ≤ 10.

Subtask 2 (20%): 0 < H, W ≤ 100.

Subtask 3 (20%): 0 < H, W ≤ 1000. However, the grid will only contain '.'s.

Subtask 4 (30%): 0 < H, W ≤ 1000. The grid will contain both 'X's and '.'s.

Sample Input 1

3 3
...
...
...

Sample Output 1

6

Sample Input 2

3 3
.X.
.X.
...

Sample Output 2

1

Sample Input 3

3 3
...
.X.
...

Sample Output 3

2

Tags

Dynamic Programming, CS3233 2013 Selection Test

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
130301s64MBMinimum
220301s64MBMinimum
320101s64MBMinimum
430301s64MBMinimum
5031s64MBMinimum

Judge Compile Command

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