Tuesday, December 9, 2014

UVa Problem 260 - Il Gioco dell'X

Problem:

Please find the problem here.

Solution:

Model the board as a graph of black nodes only with the connectivity rules given. Imagine a virtual node at the top of the graph that connect to all black nodes on the top row, and a virtual node at the bottom of the graph that connects to all black nodes on the bottom row.

Now the problem of whether black wins or not becomes a problem in graph reachability, which we can easily solve with a simple BFS. Note that we used a simple encoding of the nodes as follow, the encoding make node management particularly simple.

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17


Code:

#include "stdafx.h"

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

#include "UVa260.h"

#include <iostream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

int UVa260()
{
    int test_case_number = 0;
    while (true)
    {
        test_case_number++;
        // Step 1: Performing inputs
        int dimension;
        cin >> dimension;
        if (dimension == 0)
        {
            break;
        }
        vector<vector<char> > board;
        board.resize(dimension);
        for (int row = 0; row < dimension; row++)
        {
            board[row].resize(dimension);
            for (int col = 0; col < dimension; col++)
            {
                cin >> board[row][col];
            }
        }

        // Step 2: Build the graphs


        vector<vector<int> > black_graph;
        int num_nodes = dimension * dimension + 2;
        int goal = num_nodes - 1;
        black_graph.resize(num_nodes);

        for (int col = 0; col < dimension; col++)
        {
            if (board[0][col] == 'b')
            {
                int node_id = col + 1;
                black_graph[0].push_back(node_id);
                black_graph[node_id].push_back(0);
            }
            if (board[dimension - 1][col] == 'b')
            {
                int node_id = goal - dimension + col; // 17 - 4 + [0-3] = 13 - 16
                black_graph[goal].push_back(node_id);
                black_graph[node_id].push_back(goal);
            }
        }

        /*
        ( i-1 , j-1 ) , ( i-1 ,  j  )
        (  i  , j-1 ) , (  i  , j+1 )
        ( i+1 ,  j  ) , ( i+l , j+1 )
        */
        for (int src_row = 0; src_row < dimension; src_row++)
        {
            for (int src_col = 0; src_col < dimension; src_col++)
            {
                if (board[src_row][src_col] == 'b')
                {
                    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, 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));
                    candidates.push_back(pair<int, int>(src_row + 1, src_col + 1));
                    for (int c = 0; c < 6; c++)
                    {
                        int dst_row = candidates[c].first;
                        int dst_col = candidates[c].second;
                        if (0 <= dst_row && dst_row < dimension)
                        {
                            if (0 <= dst_col && dst_col < dimension)
                            {
                                if (board[dst_row][dst_col] == 'b')
                                {
                                    int src_id = src_row * dimension + src_col + 1;
                                    int dst_id = dst_row * dimension + dst_col + 1;

                                    // It is possible to have multiple edges, but we don't care
                                    black_graph[src_id].push_back(dst_id);
                                    black_graph[dst_id].push_back(src_id);
                                }
                            }
                        }
                    }
                }
            }
        }
#ifdef LOG
        // Debug dump the graph
        for (unsigned int i = 0; i < black_graph.size(); i++)
        {
            cout << i << ":";
            for (unsigned int j = 0; j < black_graph[i].size(); j++)
            {
                cout << " " << black_graph[i][j];
            }
            cout << endl;
        }
#endif
        vector<bool> enqueued;
        enqueued.resize(num_nodes);
        for (int i = 0; i < num_nodes; i++)
        {
            enqueued[i] = false;
        }

        queue<int> bfs_queue;
        bfs_queue.push(0);

        while (bfs_queue.size() > 0)
        {
            int current = bfs_queue.front();
            bfs_queue.pop();
            for (unsigned int neighbor_index = 0; neighbor_index < black_graph[current].size(); neighbor_index++)
            {
                int neighbor = black_graph[current][neighbor_index];
                if (!enqueued[neighbor])
                {
                    enqueued[neighbor] = true;
                    bfs_queue.push(neighbor);
                }
            }
        }

        if (enqueued[goal])
        {
            cout << test_case_number << " B" << endl;
        }
        else
        {
            cout << test_case_number << " W" << endl;
        }

    }
    return 0;
}

No comments :

Post a Comment