Connection Status:
Competition Arena > SoccerStadium

SoccerStadium

SRM 788 · 2020-07-22 · by square1001

SRM 788 · 2020-07-22 · by square1001 · Graph Theory, Greedy
Class Name: SoccerStadium
Return Type: int
Method Name: maximumGames
Arg Types: (int, int, vector<string>)
Problem Statement

Problem Statement

We have a soccer stadium. The stadium is a rectangle with height H meters and width W meters. We can imagine that it is divided into unit square cells. Rows and columns of the grid are numbered starting from zero. The cell in row i and column j is denoted (i, j).


There is a wall surrounding the stadium. More precisely, the edges of the unit squares that form the boundary of the stadium are all walls.
Additionally, some of the internal borders between pairs of cells are currently blocked using nets. Each net is 1 meter long and it is placed either horizontally or vertically between two cells.
The initial placement of nets is given in the String[] placement: a length (2*H+1) array of length (2*W+1) strings, like the one shown below. 


{ "+-+-+-+-+" ,
  "|.|.....|" ,
  "+.+-+-+-+" ,
  "|.|.|...|" ,
  "+-+-+.+.+" ,
  "|.|.|...|" ,
  "+-+.+.+-+" ,
  "|...|...|" ,
  "+-+-+-+-+" }

This is one example for H = 4, W = 4. The vertices of cells are given as '+', the vertical nets and walls are given as '|', the horizontal nets and walls as '-', and the character '.' is used everywhere else.


The surrounding wall together with the nets divide the soccer stadium into one or more connected areas. We will call these game areas.
A game area is usable if its shape is an empty rectangle. That is, the boundary of a usable game area must be completely covered by walls and nets, and there can be no nets inside the game area.


We have two goals:

  1. Our primary goal is that no space can be wasted. All game areas must be usable.
  2. Our secondary goal is that the number of game areas must be maximized, so that we can play many games in parallel.

The only type of changes we are allowed to make is that we may remove some (possibly none or all) of the nets.
Calculate and return the largest possible number of game areas we may create in the given stadium, given that all game areas must be usable.

Constraints

  • H and W will be at least 1.
  • The area of soccer stadium, H * W, will be at most 500.
  • The length of placement will be 2*H+1.
  • The length of placement[i] will be 2*W+1.
  • For even i and even j, placement[i][j] will be '+'.
  • For odd i and odd j, placement[i][j] will be '.'.
  • For even i and odd j, placement[i][j] will be '.' or '-'. The exception is for i = 0, 2*W and it will always be '-'.
  • For odd i and even j, placement[i][j] will be '.' or '|'. The exception is for j = 0, 2*H and it will always be '|'.
Examples
0)
4
4
{ "+-+-+-+-+" ,
  "|.|.....|" ,
  "+.+-+-+-+" ,
  "|.|.|...|" ,
  "+-+-+.+.+" ,
  "|.|.|...|" ,
  "+-+.+.+-+" ,
  "|...|...|" ,
  "+-+-+-+-+" }
Returns: 5

In this example, if you remove 3 nets and change stadium to as follows, the stadium can have 5 game areas, so we can play 5 games simultaneously. All game areas are rectangular, so it's a good soccer stadium. We cannot create more game areas for a good stadium. +-+-+-+-+ |.|.....| +.+-+-+-+ |.|.|...| +-+-+.+.+ |...|...| +.+.+.+.+ |...|...| +-+-+-+-+

1)
3
3
{ "+-+-+-+" ,
  "|.....|" ,
  "+-+-+.+" ,
  "|.|.|.|" ,
  "+-+-+-+" ,
  "|.|.|.|" ,
  "+-+-+-+" }
Returns: 4

In this example, if you remove 4 nets and change stadium to as follows, the stadium can have 4 game areas, so we can play 4 games simultaneously. Please note that we are NOT to maximize the number of rectangular game areas, but to maximize the number of game areas such that all of them are rectangular. +-+-+-+ |.....| +.+.+.+ |.....| +-+-+-+ |.|.|.| +-+-+-+

2)
3
3
{ "+-+-+-+" ,
  "|.|...|" ,
  "+.+-+.+" ,
  "|.|.|.|" ,
  "+.+.+-+" ,
  "|.|...|" ,
  "+-+-+-+" }
Returns: 2

In this example, you cannot create more than 2 game areas that all of them are rectangular.

3)
3
3
{ "+-+-+-+" ,
  "|.....|" ,
  "+.+-+.+" ,
  "|.|.|.|" ,
  "+.+-+.+" ,
  "|.....|" ,
  "+-+-+-+" }
Returns: 1

All game areas must be rectangular and completely empty. The outer game area currently contains four nets that form the boundary of the inner game area. This is not allowed. The only option we have is to remove all nets and make one big game area.

4)
3
4
{ "+-+-+-+-+" ,
  "|.|.|...|" ,
  "+-+-+-+-+" ,
  "|.......|" ,
  "+.+-+-+.+" ,
  "|.......|" ,
  "+-+-+-+-+" }
Returns: 4

Note that all game areas must not have extra nets which does not surround their areas.

Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SoccerStadium with a public method int maximumGames(int H, int W, vector<string> placement) · 63 test cases · 2 s / 256 MB per case

Submitting as anonymous