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

catdog Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

catdog.html

Problem Description

Mushroom Land is represented by a grid of N by M grid squares. Each grid square can be empty, '.', or an obstacle, '#'. A dog and a cat start on the top left corner of Mushroom Land, and wishes to get to the bottom right corner of Mushroom Land. At each step, they are allowed to move down or right, but as they do not like each other, their paths cannot intersect other than at the start and end points, i.e. they cannot be on the same square. Help them figure out how many possible ways both of them can travel this journey, while meeting such a condition, modulo 109 + 7.

Input

The first line of input will contain two integers, N and M.

The next N lines of input will contain M characters each, representing the grid. It is guaranteed that the top left and bottom right corner squares are empty.

Output

The output should contain one line with one integer, the total number of ways the above scenario could occur, modulo 109 + 7.

Limits

Subtask 1 (27%): 3 ≤ N, M ≤ 70.

Subtask 2 (33%): 3 ≤ N, M ≤ 300.

Subtask 3 (40%): 3 ≤ N, M ≤ 2000.

Subtask 4 (0%): Sample Testcases.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

Explanation for Sample 1

The dog can take the top path from top-left to bottom-right, and the cat can take the bottom path from top-left to bottom-right. The two can swap roles as well.

Sample Input 2

4 3
...
.#.
...
...

Sample Output 2

4

Explanation for Sample 2

The animal that takes the top path has only one path, the bottom animal has two possible paths.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
127221s256MBMinimum
233421s256MBMinimum
340621s256MBMinimum
4021s256MBMinimum

Judge Compile Command

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