USACO

USACO 5.1 Starry Night

The basic idea is to find each cluster, and then compare each cluster pair by pair. There are several sub problems to solve in this case:

  • How to represent a cluster?
    A cluster can be represented by the rectangle that covers the cluster together with the source grid (the sky). Each cluster has two key properties: the number of stars, and the covering rectangle, which can be represented by left/bottom and right/upper points.

  • How to find a cluster?
    A cluster can be found by using flood fill algorithm against the sky.

  • How to compare two clusters?
    Two clusters are obviously different if they contain different number of stars. For clusters contain same number of stars, a set of transforms need to be performed on one cluster then compare the transformed cluster with another cluster:

    • Rotate clockwise 90 degree.
    • Rotate clockwise 180 degree.
    • Rotate clockwise 270 degree.
    • Rotate clockwise 360 degree.
    • Mirror the cluster then repeat.
#include <vector>
#include <queue>
#include <iostream>
#include <fstream>

using namespace std;

int R, C;
typedef struct Cluster {
    int min_x, min_y, max_x, max_y;
    int num_of_stars;
    Cluster() : min_x(-1), min_y(-1), max_x(-1), max_y(-1), num_of_stars(0) {}
} Cluster;
typedef struct Point {
    int x; int y;
    Point(int x, int y) : x(x), y(y) {}
} Point;
vector<vector<char>> sky;
vector<vector<short>> mark;
vector<Cluster> clusters(505);
char p[550];
int idx;
void calculate_bound(int x, int y) {
    clusters[idx].min_x = clusters[idx].min_x == -1 ? x : std::min(x, clusters[idx].min_x);
    clusters[idx].min_y = clusters[idx].min_y == -1 ? y : std::min(y, clusters[idx].min_y);
    clusters[idx].max_x = clusters[idx].max_x == -1 ? x : std::max(x, clusters[idx].max_x);
    clusters[idx].max_y = clusters[idx].max_y == -1 ? y : std::max(y, clusters[idx].max_y);
}

int flood_fill(int x, int y, int index) {
    int num_of_stars = 1;
    mark[x][y] = index;
    calculate_bound(x, y);
    
    queue<Point> q;
    q.push(Point(x, y));
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        for (int i = -1; i <= 1; ++i) {
            for (int j = -1; j <= 1; ++j) {
                int xx = p.x + i, yy = p.y + j;
                if (xx < 0 || xx >= R || yy < 0 || yy >= C) continue;
                if (sky[xx][yy] != '1' || mark[xx][yy] != -1) continue;
                ++num_of_stars;
                mark[xx][yy] = index;
                calculate_bound(xx, yy);
                q.push(Point(xx, yy));
            }
        }
    }
    return num_of_stars;
}

// Rotate 90 degree clockwise.
void rotate(vector<vector<char>> &cluster, int lx, int ly) {
    int rows = (int)cluster.size(), cols = (int)cluster[0].size();
    vector<vector<char>> t(rows, vector<char>(cols));
    
    for(int i = 0; i < lx; ++i) {
        for(int j = 0; j < ly; ++j) {
            t[j][lx - i - 1] = cluster[i][j];
        }
    }
    
    for(int i = 0; i < ly; ++i) {
        for(int j = 0; j < lx; ++j) {
            cluster[i][j] = t[i][j];
        }
    }
}

void mirror(vector<vector<char>> &cluster, int lx, int ly) {
    for(int i = 0; i < lx; ++i) {
        for(int j = 0; j < ly/2; ++j) {
            swap(cluster[i][j], cluster[i][ly - 1 - j]);
        }
    }
}

bool match(int index, vector<vector<char>> cluster, int lx, int ly) {
    for(int i = 0; i < lx; ++i) {
        for(int j = 0; j < ly; ++j) {
            int xx = clusters[index].min_x + i,
                yy = clusters[index].min_y + j;
            if(mark[xx][yy] == index && cluster[i][j] == '0') return false;
        }
    }
    return true;
}

bool is_two_cluster_same(int a, int b) {
    if (clusters[a].num_of_stars != clusters[b].num_of_stars) {
        return false;
    }
    
    int ax = clusters[a].max_x - clusters[a].min_x + 1,
        ay = clusters[a].max_y - clusters[a].min_y + 1;
    int lx = clusters[b].max_x - clusters[b].min_x + 1,
        ly = clusters[b].max_y - clusters[b].min_y + 1;
    vector<vector<char>> tmp(110, vector<char>(110));
    for (int i = 0; i < lx; ++i) {
        for (int j = 0; j < ly; ++j) {
            int xx = i + clusters[b].min_x, yy = j + clusters[b].min_y;
            tmp[i][j] = sky[xx][yy];
        }
    }
    if (ax == lx && ay == ly && match(a, tmp, lx, ly)) return true;
    for(int i = 0; i < 4; ++i) {
        rotate(tmp, lx, ly);
        swap(lx, ly);
        if(ax == lx && ay == ly && match(a, tmp, lx, ly)) return true;
    }
    mirror(tmp, lx, ly);
    for(int i = 0; i < 4; ++i) {
        rotate(tmp, lx, ly);
        swap(lx, ly);
        if(ax == lx && ay == ly && match(a, tmp, lx, ly)) return true;
    }
    return false;
}

int main() {
    ifstream fin("starry.in");
    ofstream fout("starry.out");
    
    fin >> C >> R;
    sky = vector<vector<char>>(R, vector<char>(C));
    mark = vector<vector<short>>(R, vector<short>(C, -1));
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            fin >> sky[i][j];
        }
    }
    
    idx = 0;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (sky[i][j] == '1' && mark[i][j] == -1) {
                int num_of_stars = flood_fill(i, j, idx);
                clusters[idx].num_of_stars = num_of_stars;
                ++idx;
                cout << idx - 1 << " : stars " << num_of_stars << endl;
            }
        }
    }
    
    char c = 'a';
    vector<vector<char>> ans = sky;
    for(int i = 0; i < idx; ++i) {
        int index = -1;
        for(int j = 0; j < i; ++j) {
            if(is_two_cluster_same(i, j)) {
                index = j;
                cout << i << " and " << j << " same!" << endl;
                break;
            }
        }
        if(index != -1)  {
            p[i] = p[index];
        } else {
            p[i] = c++;
        }
        for(int ii = clusters[i].min_x; ii <= clusters[i].max_x; ++ii) {
            for(int jj = clusters[i].min_y; jj <= clusters[i].max_y; ++jj) {
                if(mark[ii][jj] == i) {
                   ans[ii][jj] = p[i];
                }
            }
        }
    }
    
    for(int i = 0; i < R; ++i) {
        for(int j = 0; j < C; ++j) {
            fout << ans[i][j];
            cout << ans[i][j];
        }
        fout << endl;
        cout << endl;
    }
}