2016 Jan Platinum Problem 1 Fort Moo

Official Problem Statement

Fort Moo

Problem

In this problem, the cows are building a fort with dimensions N x M (1 ≤ N, M ≤ 200). The fort is made up of cells and each cell can either contain a wall (denoted by an 'X') or be empty (denoted by a '.'). An empty cell means that a cow can see through that cell. The fort must be a rectangle and it should be built in such a way that all cells within it are empty. The task is to find the area of the largest such fort that can be built.

Solution

This problem can be solved using dynamic programming and prefix sums.

Firstly, for each cell, compute the largest rectangle that can be built with the cell as the upper left corner. This can be done in a bottom-up manner starting from the bottom of the grid. For each row, keep track of the longest streak of empty cells and update it as you move to the right. For each column, compute the prefix sum of streaks. This will help to determine whether a given subrectangle is valid or not.

Next, iterate over all pairs of rows. For each pair, calculate the maximum area of a fort that can be constructed between these two rows. This can be done by maintaining two arrays. One array keeps track of the largest streak for each column and the other keeps track of the maximum area that can be constructed.

Finally, the answer to the problem is the maximum area found over all pairs of rows.

This solution runs in O(N^2 * M) time which is fast enough given the constraints of the problem.

Please note that a careful implementation is needed to handle the edge cases correctly. For instance, when computing the streaks, you need to ensure that the streaks are reset correctly when you encounter a wall. Similarly, when computing the maximum area, you need to consider whether the entire width of the fort is clear of walls or not.

Code

C++

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

int num(vector<vector<int>>& grid, int a, int b, int c, int d) {
    return grid[c+1][d+1] - grid[a][d+1] - grid[c+1][b] + grid[a][b];
}

vector<vector<int>> processInput(int n, int m) {
    vector<vector<int>> grid(n+1, vector<int>(m+1, 0));
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < m; j++) {
            grid[i+1][j+1] = grid[i][j+1] + grid[i+1][j] - grid[i][j];
            if(s[j] == 'X') {
                grid[i+1][j+1]++;
            }
        }
    }
    return grid;
}

int computeMaxArea(vector<vector<int>>& grid, int n, int m) {
    int ret = 0;
    for(int j = 0; j < m; j++) {
        for(int k = j; k < m; k++) {
            int lastRow = -1;
            for(int i = 0; i < n; i++) {
                bool validRow = num(grid, i, j, i, k) == 0;
                if(validRow) {
                    ret = max(ret, k-j+1);
                }
                if(validRow && lastRow >= 0) {
                    ret = max(ret, (i - lastRow+1) * (k-j + 1));
                }
                if(num(grid, i, k, i, k) > 0 || num(grid, i, j, i, j) > 0) {
                    lastRow = -1;
                }
                if(validRow && lastRow == -1) {
                    lastRow = i;
                }
            }
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    // Process the input
    auto grid = processInput(n, m);

    // Compute the maximum area
    auto maxArea = computeMaxArea(grid, n, m);

    // Output the result
    cout << maxArea << "\n";

    return 0;
}

Java

import java.io.*;
import java.util.*;

public class FortMoo {
    
    private static int num(int[][] grid, int a, int b, int c, int d) {
        return grid[c+1][d+1] - grid[a][d+1] - grid[c+1][b] + grid[a][b];
    }

    private static int[][] processInput(BufferedReader br, int n, int m) throws IOException {
        int[][] grid = new int[n+1][m+1];
        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            for(int j = 0; j < m; j++) {
                grid[i+1][j+1] = grid[i][j+1] + grid[i+1][j] - grid[i][j];
                if(s.charAt(j) == 'X') {
                    grid[i+1][j+1]++;
                }
            }
        }
        return grid;
    }

    private static long computeMaxArea(int[][] grid, int n, int m) {
        long ret = 0;
        for(int j = 0; j < m; j++) {
            for(int k = j; k < m; k++) {
                int lastRow = -1;
                for(int i = 0; i < n; i++) {
                    boolean validRow = num(grid, i, j, i, k) == 0;
                    if(validRow) {
                        ret = Math.max(ret, k-j+1);
                    }
                    if(validRow && lastRow >= 0) {
                        ret = Math.max(ret, (i - lastRow+1) * (k-j + 1));
                    }
                    if(num(grid, i, k, i, k) > 0 || num(grid, i, j, i, j) > 0) {
                        lastRow = -1;
                    }
                    if(validRow && lastRow == -1) {
                        lastRow = i;
                    }
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("fortmoo.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("fortmoo.out")));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        // Process the input
        int[][] grid = processInput(br, n, m);

        // Compute the maximum area
        long maxArea = computeMaxArea(grid, n, m);
        
        // Output the result
        pw.println(maxArea);
        pw.close();
    }
}

Python

def num(grid, a, b, c, d):
    return grid[c+1][d+1] - grid[a][d+1] - grid[c+1][b] + grid[a][b]

def process_input(n, m):
    grid = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n):
        s = input().strip()
        for j in range(m):
            grid[i+1][j+1] = grid[i][j+1] + grid[i+1][j] - grid[i][j]
            if s[j] == 'X':
                grid[i+1][j+1] += 1
    return grid

def compute_max_area(grid, n, m):
    ret = 0
    for j in range(m):
        for k in range(j, m):
            last_row = -1
            for i in range(n):
                valid_row = num(grid, i, j, i, k) == 0
                if valid_row:
                    ret = max(ret, k-j+1)
                if valid_row and last_row >= 0:
                    ret = max(ret, (i - last_row+1) * (k-j + 1))
                if num(grid, i, k, i, k) > 0 or num(grid, i, j, i, j) > 0:
                    last_row = -1
                if valid_row and last_row == -1:
                    last_row = i
    return ret

def main():
    n, m = map(int, input().split())
    grid = process_input(n, m)
    max_area = compute_max_area(grid, n, m)
    print(max_area)

if __name__ == "__main__":
    main()