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

toxicwaste Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

toxicwaste.html

Problem Description

Squeaky the Rat has left some barrels of toxic waste from his experiments out on his lawn of N by M units.

Coco the Playful Monkey has tipped the barrels over, resulting in toxic waste spilling all over the lawn.

Toxic waste is dangerous, as they can cause bananas to mutate and then bananas will take over the world.

Luckily, Kraw the Scientific Krow happens to have some extra high grade lead planks of all lengths which can contain the damage. Every lead plank has a width of 1 unit, but each plank can be as long as you want.

Each lead plank, when placed, can overlap other lead planks. However, no lead planks can be placed on any spot where there is no toxic waste as Squeaky the Rat will be angry at you for unnecessarily causing more damage to his lawn.

Kraw the Krow charges you 1 dollar for each lead plank. Find the minimum cost that must be paid to cover all the toxic waste.

Input

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

The next N lines of input will contain M characters each. If the character is 'x', it means that there is toxic waste on that spot. If the character is '.', it means there is no toxic waste on that spot.

Output

The output should contain one integer, the minimum amount of money required to cover all the toxic waste.

Limits

Subtask 1 (12%): N = 2. 1 ≤ M ≤ 50.

Subtask 2 (8%): There will only be 'x'.

Subtask 3 (19%): N = 3. 1 ≤ M ≤ 5.

Subtask 4 (61%): 1 ≤ N, M ≤ 50.

Subtask 5 (0%): Sample Testcases

Sample Testcase 1

Input

3 3
xxx
.x.
xxx

Output

3

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
112251s64MBMinimum
28101s64MBMinimum
319251s64MBMinimum
461501s64MBMinimum
5011s64MBMinimum

Judge Compile Command

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