10279

10279.cpp

#include "gtest\gtest.h"
#include <iostream>
#include <vector>
#include "DangerSweeper.h"

using namespace std;

int main(int argc, char* argv[])
{
    //testing::InitGoogleTest(&argc, argv);
    //RUN_ALL_TESTS();

    int a;
    cin >> a;

    for (int i = 0; i < a; i++)
    {
        int b;
        cin >> b;
        bool bomb(false);

        vector<vector<size_t>> map;
        for (int j = 0; j < b; j++)
        {
            vector<size_t> map_row;
            for (int k = 0; k < b; k++)
            {
                char c;
                cin >> c;
                map_row.push_back((c == '.') ? 0 : 1);
            }
            map.push_back(map_row);
        }

        vector<vector<bool>> mask;
        for (int j = 0; j < b; j++)
        {
            vector<bool> mask_row;
            for (int k = 0; k < b; k++)
            {
                char c;
                cin >> c;
                mask_row.push_back((c == '.') ? false : true);
                if (!bomb) bomb = (c == '.') ? false : (map[j][k]==1);
            }
            mask.push_back(mask_row);
        }

        DangerSweeper DS;
        DS.set_map(map);
        DS.detect();

        if (!bomb)
        {
            for (size_t j = 0; j < mask.size(); j++)
            {
                for (size_t k = 0; k < mask.size(); k++)
                {
                    //cout << mask[j][k] ? DS.get_report()[j][k] : '.';
                    if (mask[j][k])
                    {
                        cout << DS.get_report()[j][k];
                    }
                    else
                    {
                        cout << '.';
                    }
                }
                cout << endl;
            }
        }
        else
        {
            for (size_t j = 0; j < mask.size(); j++)
            {
                for (size_t k = 0; k < mask.size(); k++)
                {
                    //cout << (map[j][k] == 1) ? '*' : mask[j][k] ? DS.get_report()[j][k] : '.';
                    if (map[j][k] == 0)
                    {
                        if (mask[j][k])
                        {
                            cout << DS.get_report()[j][k];
                        }
                        else
                        {
                            cout << '.';
                        }
                    }
                    else
                    {
                        cout << '*';
                    }
                }
                cout << endl;
            }
        }

        if (a -1 != i) cout << endl;
    }

    return 0;
}

DangerSweeper.cpp

#include "DangerSweeper.h"

void DangerSweeper::set_map(const std::vector<std::vector<size_t>> & map)
{
    size_t expand_size = (mask().size() - 1) / 2;
    size_t length = map.size() + expand_size * 2;

    std::vector<size_t> map_zero_row(length, 0);

    for (size_t i = 0; i < expand_size; i++)
    {
        m_map.push_back(map_zero_row);
    }

    for (size_t i = 0; i < length - expand_size * 2; i++)
    {
        std::vector<size_t> map_temp;
        for (size_t j = 0; j < expand_size; j++)
        {
            map_temp.push_back(0);
        }

        for (size_t j = 0; j < map.size(); j++)
        {
            map_temp.push_back(map[i][j]);
        }

        for (size_t j = 0; j < expand_size; j++)
        {
            map_temp.push_back(0);
        }
        m_map.push_back(map_temp);
    }

    for (size_t i = 0; i < expand_size; i++)
    {
        m_map.push_back(map_zero_row);
    }
}

std::vector<std::vector<size_t>> DangerSweeper::convolution(const std::vector<std::vector<size_t>> & input, const std::vector<std::vector<size_t>> & mask) const
{
    std::vector<std::vector<size_t>> result;

    if (  input.size() <= 0
       || mask.size() <= 0
       || mask.size() > input.size()
       || (mask.size() % 2) == 0
       )
    {
        return result;
    }

    size_t mask_center = mask.size() / 2;

    for (size_t i = 0; i < input.size(); i++)
    {
        std::vector<size_t> temp;
        for (size_t j = 0; j < input[i].size(); j++)
        {
            if (  i < mask_center
               || j < mask_center
               || i >= input.size() - mask_center
               || j >= input[i].size() - mask_center
               )
            {
                temp.push_back(0);
                continue;
            }

            size_t temp_y = i - mask_center;
            size_t temp_x = j - mask_center;
            size_t temp_result(0);
            for (size_t k = 0; k < mask.size(); k++)
            {
                for (size_t l = 0; l < mask[k].size(); l++)
                {
                    temp_result += input[temp_y + k][temp_x + l] * mask[k][l];
                }
            }
            temp.push_back(temp_result);
        }
        result.push_back(temp);
    }

    return result;
}

void DangerSweeper::detect()
{
    m_report = remove_noise(convolution(m_map, mask()));
}

std::vector<std::vector<size_t>> DangerSweeper::remove_noise(const std::vector<std::vector<size_t>> & map)
{
    size_t expand_size = (mask().size() - 1) / 2;
    size_t center_length = m_map.size() - expand_size * 2;

    std::vector<std::vector<size_t>> temp(center_length, std::vector<size_t>(center_length,0));

    for (size_t i = 0; i < center_length; i++)
    {
        for (size_t j = 0; j < center_length; j++)
        {
            temp[i][j] = map[i + expand_size][j + expand_size];
        }
    }

    return temp;
}

DangerSweeper.h

#include <vector>

class DangerSweeper
{
public:
    DangerSweeper(){};
    void set_map(const std::vector<std::vector<size_t>> & map);
    std::vector<std::vector<size_t>> get_report() { return m_report; };
    std::vector<std::vector<size_t>> convolution(const std::vector<std::vector<size_t>> & map, const std::vector<std::vector<size_t>> & mask) const;
    void detect();

private:
    std::vector<std::vector<size_t>> m_map;
    std::vector<std::vector<size_t>> m_report;
    static const std::vector<std::vector<size_t>> mask()
    {
        static const std::vector<std::vector<size_t>> mask =
        {
            { 1, 1, 1 },
            { 1, 0, 1 },
            { 1, 1, 1 }
        };

        return mask;
    }
    std::vector<std::vector<size_t>> remove_noise(const std::vector<std::vector<size_t>> & map);
};

test10279.cpp

#pragma once
#include <gtest\gtest.h>
#include <vector>
#include "DangerSweeper.h"

TEST(ConvolutionTest, ConvolutionTest)
{
    std::vector<std::vector<size_t>> input = 
    {
        { 1, 2, 3, 4, 5 },
        { 1, 2, 3, 4, 5 },
        { 1, 2, 3, 4, 5 },
        { 1, 2, 3, 4, 5 },
        { 1, 2, 3, 4, 5 }
    };

    std::vector<std::vector<size_t>> mask =
    {
        { 1, 1, 1 },
        { 1, 0, 1 },
        { 1, 1, 1 }
    };

    std::vector<std::vector<size_t>> output =
    {
        { 0, 0, 0, 0, 0 },
        { 0, 16, 24, 32, 0 },
        { 0, 16, 24, 32, 0 },
        { 0, 16, 24, 32, 0 },
        { 0, 0, 0, 0, 0 }
    };

    DangerSweeper test;
    EXPECT_EQ(output, test.convolution(input, mask));

    std::vector<std::vector<size_t>> mask2 =
    {
        { 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1 },
        { 1, 1, 0, 1, 1 },
        { 1, 1, 1, 1, 1 },
        { 1, 1, 1, 1, 1 }
    };

    std::vector<std::vector<size_t>> output2 =
    {
        { 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0 },
        { 0, 0, 72, 0, 0 },
        { 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0 }
    };

    EXPECT_EQ(output2, test.convolution(input, mask2));
}