Thursday, December 11, 2014

UVa Problem 352 - The Seasonal War

Problem:

Please find the problem here.

Solution:

A perfect case for disjoint set union find! Model the image as a graph. Use disjoint set union find to find the connected components, that's it!

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=288

#include "UVa352.h"

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int UVa352_find(vector<int>& sets, int i)
{
    if (sets[i] < 0)
    {
        return i;
    }
    else
    {
        int result = UVa352_find(sets, sets[i]);
        sets[i] = result;
        return result;
    }
}

int UVa352()
{
    int test_case_number = 0;
    while (true)
    {
        test_case_number++;
        // Step 1: Read input
        int dimension;
        cin >> dimension;
        if (cin.eof())
        {
            break;
        }

        vector<vector<int> > image;
        image.resize(dimension);
        for (int row = 0; row < dimension; row++)
        {
            image[row].resize(dimension);
            char c;
            for (int col = 0; col < dimension; col++)
            {
                cin >> c;
                image[row][col] = c - '0';
            }
        }

        // Step 2: Disjoint set union find
        // Goal - count the number of sets
        // Each cell with a 1 is a set, union all the connected sets

        // Step 2.1: Construct the data structure (and index, and a vector representing the sets)
        int number_of_sets = 0;

        vector<vector<int> > index;
        vector<int> sets;
        index.resize(dimension);
        for (int row = 0; row < dimension; row++)
        {
            index[row].resize(dimension);
            for (int col = 0; col < dimension; col++)
            {
                if (image[row][col] == 1)
                {
                    index[row][col] = number_of_sets++;
                }
            }
        }
        sets.resize(number_of_sets);

        for (int i = 0; i < number_of_sets; i++)
        {
            // All sets have size 1
            sets[i] = -1;
        }

        // Step 2.2: Performing the union operations
        for (int src_row = 0; src_row < dimension; src_row++)
        {
            for (int src_col = 0; src_col < dimension; src_col++)
            {
                if (image[src_row][src_col] == 1)
                {
                    int src_index = index[src_row][src_col];
                    vector<pair<int, int> > candidates;
                    candidates.push_back(pair<int, int>(src_row - 1, src_col - 1));
                    candidates.push_back(pair<int, int>(src_row - 1, src_col));
                    candidates.push_back(pair<int, int>(src_row - 1, src_col + 1));
                    candidates.push_back(pair<int, int>(src_row, src_col - 1));
                    candidates.push_back(pair<int, int>(src_row, src_col + 1));
                    candidates.push_back(pair<int, int>(src_row + 1, src_col - 1));
                    candidates.push_back(pair<int, int>(src_row + 1, src_col));
                    candidates.push_back(pair<int, int>(src_row + 1, src_col + 1));
                    for (unsigned ci = 0; ci < candidates.size(); ci++)
                    {
                        int dst_row = candidates[ci].first;
                        int dst_col = candidates[ci].second;
                        if (0 <= dst_row && dst_row < dimension)
                        {
                            if (0 <= dst_col && dst_col < dimension)
                            {
                                if (image[dst_row][dst_col] == 1)
                                {
                                    int dst_index = index[dst_row][dst_col];
                                    int src_root = UVa352_find(sets, src_index);
                                    int dst_root = UVa352_find(sets, dst_index);

                                    if (src_root != dst_root)
                                    {
                                        if (sets[src_root] < sets[dst_root]) // src_index is a larger set
                                        {
                                            sets[src_root] = sets[src_root] + sets[dst_root];
                                            sets[dst_root] = src_root;
                                        }
                                        else 
                                        {
                                            sets[dst_root] = sets[src_root] + sets[dst_root];
                                            sets[src_root] = dst_root;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        // Step 2.3: Extract the number of sets
        int num_sets = 0;
        for (unsigned i = 0; i < sets.size(); i++)
        {
            if (sets[i] < 0)
            {
                num_sets++;
            }
        }

        // Step 3: Output
        cout << "Image number " << test_case_number << " contains " << num_sets <<" war eagles." << endl;
        
    }


    return 0;
}

No comments :

Post a Comment