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

discozoo Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

discozoo.html

Problem Description

Bradley has recently been addicted to this game of Disco Zoo.



In this game, there is a rescue portion, where you have to "go to the forest" to "rescue animals". Each animal has a specific pattern. For example, in the example you see above, the rabbit has a pattern of four in a vertical column. Bradley, playing a variant of this game, is "rescuing animals" in a grid of size H x W, and is attempting to find one animal of a specific pattern (possibly the one you see above). In addition, Bradley has also explored some grid squares and found no animals to be there, thus the pattern of that animal cannot enter into those squares. Given a grid containing the pattern of the animal Bradley is finding, and another grid representing the area Bradley has explored (or not explored), Bradley wonders how many possible positions the animals can possibly be in.

Input

The first line of input contains two integers, H and W.
The next H lines of W characters contains either a '.' or a 'X', with a 'X' representing an area Bradley has explored and an '.' representing otherwise.
The following line of input contains two integers, A and B, the height and width of the grid that will contain one pattern of the animal Bradley is trying to find.
The next A lines of input will contain B characters each, being either a '.' or an 'A', with a '.' representing an empty area while an 'A' represents a grid that is part of the animal pattern.
Please note that the animal's shape will always be convex and may not cover the entire grid.

Output

Your output should contain one integer, the number of possible positions the animal could still possibly be in.

Limits

Subtask 1 (24%): 1 ≤ H, W, A, B ≤ 10.
Subtask 2 (27%): 1 ≤ H, W, A, B ≤ 100.
Subtask 3 (49%): 1 ≤ H, W, A, B ≤ 1000.
Subtask 4 (0%): As per sample testcases.

Sample Input 1

5 5
.X...
.X...
.X...
.XXXX
.....
4 5
.....
.AAA.
.AAA.
.....

Sample Output 1

2

Explanation for Sample 1

Possible positions:
.XAAA .X...
.XAAA .XAAA
.X... .XAAA
.XXXX .XXXX
..... .....

discozoo.png

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
124201s32MBMinimum
227401s32MBMinimum
349601s32MBMinimum
4011s32MBMinimum

Judge Compile Command

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