USACO 2017 US Open Contest Bronze Division - Modern Art

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Find all borders of rectangles and then run brute force for each permutation. There are better solutions too, present in other versions across divisions.

Source codes

The source code in C++ can be seen below.

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

int main()
{
    ifstream cin("art.in");
    ofstream cout("art.out");

    int n;
    cin >> n;

    vector<vector<char> > v(n+1, vector<char> (n+1));

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> v[i][j];

    vector<int> is(10);
    vector<int> minx(10, 11), maxx(10), miny(10, 11), maxy(10);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            int x = v[i][j] - '0';
            is[x]++;
            minx[x] = min(minx[x], i);
            maxx[x] = max(maxx[x], i);
            miny[x] = min(miny[x], j);
            maxy[x] = max(maxy[x], j);
        }

    vector<int> numbers;
    for(int i = 1; i <= 9; i++)
        if(is[i])
            numbers.push_back(i);

    vector<int> first(10);
    do{
        bool valid = 1;
        vector<int> viz(10);
        for(int i = 0; valid && i < (int) numbers.size(); i++)
        {
            viz[numbers[i]] = 1;
            for(int xx = minx[numbers[i]]; xx <= maxx[numbers[i]]; xx++)
                for(int yy = miny[numbers[i]]; yy <= maxy[numbers[i]]; yy++)
                {
                    if(v[xx][yy] == '0');
                    else
                        if(!viz[v[xx][yy] - '0'])
                            valid = 0;
                }
        }
        if(valid)
            first[numbers.back()] = 1;
    }while(next_permutation(numbers.begin(), numbers.end()));
    int cnt = 0;
    for(int i = 1; i <= 9; i++)
        cnt += first[i];
    cout << cnt;
    return 0;
}