Monday, October 6, 2014

UVa Problem 639 - Don't Get Rooked

Problem:

Please find the problem here.

Solution:

If we model each position as a node and the capture relationship as an edge. The problem ask for the maximum independent set.

To solve the maximum independent set problem, we use the recursive backtracking again. Try each available position (i.e. those that are not wall and not captured yet). Capture all the captured position, and then solve the sub-problem.

The key to solve this problem efficiently is to avoid copying. Instead of copying the board (which in this instance small it doesn't matter much), we remember the captured now pieces so that we can undo the move, that allow us to use one board throughout the whole process.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=580

#include "UVa639.h"

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

struct position
{
    int row;
    int col;
    bool occupied;
    list<position*> captures;
};

void find_configurations(vector<position*>& blank_positions, int placed, int& max_configuration)
{
    bool found = false;
    // Step 3.1: Finding a blank position
    for (vector<position*>::iterator bi = blank_positions.begin(); bi != blank_positions.end(); bi++)
    {
        position* current = *bi;
        if (!current->occupied)
        {
            // Step 3.2: Trying the current position
            current->occupied = true;
            found = true;

            // Step 3.3: Capture - and remember only the list we change the flag (we don't want to uncapture those that we don't)
            list<position*> captured_now;
            for (list<position*>::iterator ci = current->captures.begin(); ci != current->captures.end(); ci++)
            {
                position* try_capture_now = *ci;
                if (!try_capture_now->occupied)
                {
                    captured_now.push_back(try_capture_now);
                    try_capture_now->occupied = true;
                }
            }
            find_configurations(blank_positions, placed + 1, max_configuration);
            
            // Step 3.4: Undo the move and try another one
            for (list<position*>::iterator ri = captured_now.begin(); ri != captured_now.end(); ri++)
            {
                (*ri)->occupied = false;
            }
            current->occupied = false;
        }
    }
    if (!found)
    {
        // Step 3.5: There is no way to place more rooks - this is a maximal configuration
        max_configuration = max(placed, max_configuration);
    }
}

int UVa639()
{
    while (true)
    {
        // Step 1: Read input
        int board_size;
        cin >> board_size;
        if (board_size == 0)
        {
            break;
        }
        char board[4][4];
        for (int i = 0; i < board_size; i++)
        {
            for (int j = 0; j < board_size; j++)
            {
                cin >> board[i][j];
            }
        }

        // Step 2: Build the capture graph

        // Step 2.1: Build the positions
        position positions[4][4];
        vector<position*> blank_position;
        for (int i = 0; i < board_size; i++)
        {
            for (int j = 0; j < board_size; j++)
            {
                positions[i][j].row = i;
                positions[i][j].col = j;
                positions[i][j].occupied = (board[i][j] == 'X');
                if (!positions[i][j].occupied)
                {
                    blank_position.push_back(&positions[i][j]);
                }
            }
        }

        // Step 2.2: Deduce capture relationship
        for (unsigned int i = 0; i < blank_position.size(); i++)
        {
            for (unsigned int j = i + 1; j < blank_position.size(); j++)
            {
                if (blank_position[i]->row == blank_position[j]->row)
                {
                    int row = blank_position[i]->row;
                    int minCol = min(blank_position[i]->col, blank_position[j]->col);
                    int maxCol = max(blank_position[i]->col, blank_position[j]->col);
                    bool capture = true;
                    for (int c = minCol; c <= maxCol; c++)
                    {
                        if (board[row][c] == 'X')
                        {
                            capture = false;
                        }
                    }
                    if (capture)
                    {
                        blank_position[i]->captures.push_back(blank_position[j]);
                        blank_position[j]->captures.push_back(blank_position[i]);
                    }
                }
                else if (blank_position[i]->col == blank_position[j]->col)
                {
                    int col = blank_position[i]->col;
                    int minRow = min(blank_position[i]->row, blank_position[j]->row);
                    int maxRow = max(blank_position[i]->row, blank_position[j]->row);
                    bool capture = true;
                    for (int r = minRow; r <= maxRow; r++)
                    {
                        if (board[r][col] == 'X')
                        {
                            capture = false;
                        }
                    }
                    if (capture)
                    {
                        blank_position[i]->captures.push_back(blank_position[j]);
                        blank_position[j]->captures.push_back(blank_position[i]);
                    }
                }
            }
        }

        // Step 3: Recursive backtracking in action
        int max_configuration = -1;
        find_configurations(blank_position, 0, max_configuration);
        cout << max_configuration << endl;
    }

    return 0;
}

No comments :

Post a Comment