yipo
8/20/2018 - 4:35 PM

uva10189

Minesweeper

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
class matrix
{
public:
    matrix(size_t row, size_t col, const T& value = T()) :
        m_buf(row*col, value),
        m_row(row),
        m_col(col)
    {
    }

    size_t row() const
    {
        return m_row;
    }

    size_t col() const
    {
        return m_col;
    }

    const T& at(size_t i, size_t j) const
    {
        return m_buf.at(i*m_col + j);
    }

    T& at(size_t i, size_t j)
    {
        return m_buf.at(i*m_col + j);
    }

private:
    vector<T> m_buf;
    size_t m_row, m_col;
};

using BOOL = char;

matrix<size_t> gen_heat_map(const matrix<BOOL>& m, size_t radius)
{
    matrix<size_t> temp(m.row() + radius, m.col() + radius, 0);

    for (size_t i = 0; i < m.row(); i++)
    {
        for (size_t j = 0; j < m.col(); j++)
        {
            temp.at(i, j) = m.at(i, j) ? 1 : 0;
        }
    }

    for (size_t i = 0; i < temp.row(); i++)
    {
        for (size_t j = 0; j < temp.col(); j++)
        {
            if (j > 0) temp.at(i, j) += temp.at(i, j - 1);
        }
    }
    for (size_t i = 0; i < temp.row(); i++)
    {
        for (size_t j = 0; j < temp.col(); j++)
        {
            if (i > 0) temp.at(i, j) += temp.at(i - 1, j);
        }
    }

    matrix<size_t> result(m.row(), m.col());
    const size_t diameter = 2 * radius + 1;

    for (size_t i = 0; i < result.row(); i++)
    {
        for (size_t j = 0; j < result.col(); j++)
        {
            auto& value = result.at(i, j);
            auto p = i + radius, q = j + radius;

            value = temp.at(p, q);
            if (p >= diameter && q >= diameter) value += temp.at(p - diameter, q - diameter);
            if (p >= diameter) value -= temp.at(p - diameter, q);
            if (q >= diameter) value -= temp.at(p, q - diameter);
        }
    }
    return result;
}

bool test_case(size_t test_num)
{
    size_t row, col;
    cin >> row >> col;

    if (row == 0 && col == 0) return false;

    matrix<BOOL> has_mine(row, col, false);

    for (size_t i = 0; i < has_mine.row(); i++)
    {
        for (size_t j = 0; j < has_mine.col(); j++)
        {
            while (cin.peek() != EOF && isspace(cin.peek())) cin.get();
            auto ch = cin.get();

            if (ch == EOF) return false;
            has_mine.at(i, j) = (ch == '*');
        }
    }

    auto heat_map = gen_heat_map(has_mine, 1);

    if (test_num >= 2) cout << endl;
    cout << "Field #" << test_num << ":" << endl;

    for (size_t i = 0; i < heat_map.row(); i++)
    {
        for (size_t j = 0; j < heat_map.col(); j++)
        {
            cout << (has_mine.at(i, j) ? "*" : to_string(heat_map.at(i, j)));
        }
        cout << endl;
    }

    return true;
}

int main()
{
    size_t num = 1;
    while (test_case(num++));
    return 0;
}