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

flooding Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

flooding.html

Problem Description

A town is experiencing heavy rains and flooding. This town can be described as a grid with N rows and M columns, with each grid square either being '.', an empty space or a 'X', a wall.

The heavy rain is currently falling at one particular spot marked as 'R' on the grid. Walls stop waters, so flooding will occur on any empty grid square directly or indirectly connected to the 'R' square. Water can only flow in four directions: up, down, left or right.

Rar is evil, and decides to break down one of the walls to make the flood worse. More specifically, he wishes to change at most one of the 'X' squares (there may be none) into a '.' square, in order to maximise the number of grid squares eventually flooded by the rainwaters.

Help Rar determine the maximum number of possible grid squares he could flood.

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.

Output

Output a single line containing a single integer, the maximum number of grid squares that could be flooded.

Limits

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

Subtask 2 (25%): 1 ≤ N, M ≤ 300.

Subtask 3 (46%): 1 ≤ N, M ≤ 1 000.

Subtask 4 (0%): Sample Testcases.

Sample Testcase 1

Input

4 4
..R.
X..X
XXXX
....

Output

11

Sample Testcase 2

Input

4 4
X...
XXXR
.XXX
...X

Output

5

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
129221s256MBMinimum
225421s256MBMinimum
346621s256MBMinimum
4021s256MBMinimum

Judge Compile Command

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