Algorithm


 problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1608

Consider a n × n chessboard. The term block(r1, c1, r2, c2) denotes the rectangular subset of squares defined by the intersection of rows {r1, r1 + 1, . . . , r2} and columns {c1, c1 + 1, . . . , c2}. There are several occupied blocks on the board. We are interested in the largest block (in the sense of maximum area) that can be placed in the free space remaining in the board. For example, in a chessboard of size 10, if block(2, 2, 5, 3), block(8, 3, 9, 7), and block(3, 6, 3, 8) represent occupied space, then the largest block that can be placed in free space has area 28. This can be visually checked in the following figure: r\c 1 2 3 4 5 6 7 8 9 10 1 2 X X 3 X X X X X 4 X X o o o o o o o 5 X X o o o o o o o 6 o o o o o o o 7 o o o o o o o 8 X X X X X 9 X X X X X 10 We are interested only in the area of the largest free block, and not in its particular location. Therefore, each instance of the problem has a unique solution. Input The program first reads the number p of instances of the problem. Each instance is described by the size s of the board, the number b of blocks of occupied space, and the vertices r1, c1, r2, c2, of each block: p number of problem instances in the file s (board size) instance #1 n (number of blocks) r1 c1 r2 c2 (first block) r1 c1 r2 c2 (second block) . . . . . . r1 c1 r2 c2 (n-th block) s (board size) instance #2 n (number of blocks) r1 c1 r2 c2 (first block) r1 c1 r2 c2 (second block) . . . . . . r1 c1 r2 c2 (n-th block) . . . . . . instance #p Assumptions: • 1 ≤ s ≤ 100 • 0 ≤ b ≤ 100 • 1 ≤ r1 ≤ r2 ≤ s • 1 ≤ c1 ≤ c2 ≤ s • Occupied blocks may overlap. Output For each test case the output consists of a integer indicating the area of the largest block that can be located in the available free squares.

Sample Input 3 10 3 2 2 5 3 8 3 9 7 3 6 3 8 20 1 1 1 1 1 10 2 5 1 5 10 1 5 10 5

Sample Output 28 380 25

Code Examples

#1 Code Example with C Programming

Code - C Programming

#include <bits/stdc++.h>
using namespace std;

// alternate method to solve it more efficiently is to use stack
// compute 'largest zero histogram' for each row O(N^2)

int main()
{
    int t,n,b,r1,c1,r2,c2;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&b);
        vector < vector<int>> commands(n+2,vector<int>(n+2));
        vector < vector<int>> dp(n+1,vector<int>(n+1));
        while(b--){
            scanf("%d %d %d %d",&r1,&c1,&r2,&c2);
            // transform into representation that can be derived
            commands[r1][c1] += 1;
            commands[r2+1][c1] -= 1;
            commands[r1][c2+1] -= 1;
            commands[r2+1][c2+1] += 1;
        }
        for(int i=1;i < =n;i++) for(int j=1;j < =n;j++){
            // derive original array and perform dp
            commands[i][j] += (commands[i-1][j]+commands[i][j-1]-commands[i-1][j-1]);
            dp[i][j] = commands[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
        }
        int res = 0;
        for(int i=1;i < =n;i++) for(int j=1;j < =n;j++)
        for(int k=i;k < =n;k++) for(int l=j;l < =n;l++){
            int cur = dp[k][l]-dp[k][j-1]-dp[i-1][l]+dp[i-1][j-1];
            if(cur == 0)
                res = max(res,(k-i+1)*(l-j+1));
        }
        printf("%d\n",res);
    }
}

Copy The Code & Try With Live Editor

Input

x
+
cmd
3
10
3
2 2 5 3
8 3 9 7
3 6 3 8
20
1
1 1 1 1
10
2
5 1 5 10
1 5 10 5

Output

x
+
cmd
28
380
25
Advertisements

Demonstration


UVA Online Judge solution  - 10667-Largest Block - UVA Online Judge solution in C,C++,java

Previous
UVA Online Judge solution - 10664-Luggage - UVA Online Judge solution in C,C++,java
Next
UVA Online Judge solution - 10670-Work Reduction - UVA Online Judge solution in C,C++,java