Решение японской головоломки нурикабе на c++

#include <iostream>
using namespace std;
 
int ** Create( size_t n, size_t m ) {
    int ** M = new int * [n];
    for ( size_t i = 0; i < n; ++i ) {
        M[i] = new int [m];
    }
    return M;
}
 
void Input( int ** M, size_t n, size_t m ) {
    for ( size_t i = 0; i < n; ++i ) {
        for ( size_t j = 0; j < m; ++j ) {
            cin >> M[i][j];
        }
    }
    cin.get();
}
 
void print (int ** M, size_t n, size_t m){
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++)
            cout << M[i][j] << ' ';
        cout << '\n';
    }
}
bool isvalidsolution (int** margin, size_t n, size_t m){
    //реализация проверки правил
    return 0; //или 1 если решено верно
}
 
//рекурсивная функция для решения головоломки
void solvenuricabe (int** margin, size_t n, size_t m){
    //если достигнут конец доски вызвать ф-ю проверки
    
    //логика для перербора всех возможных вариантов установки острова
    
    //если остров нарушает правила то рекурсивно вызываем функцию но на
    //этот раз остров должен быть другим
}
 
int main (){
    int n;
    cin >> n;
    int** margin = Create(n, n);
    Input(margin, n, n);
    solvenuricabe(margin, n, n);
    print(margin,n,n)
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <ranges>
#include <set>
#include <map>
#include <cmath>
#include <iterator>
#include <queue>
namespace rng = std::ranges;
 
using coord_t = std::pair<int, int>; // координата в матрице: {row, column}
using vcoord = std::vector<coord_t>;
using scoord = std::set<coord_t>;
 
// исходная матрица 
std::vector<std::vector<int>> mtx; 
// вспомогательная матрица. Здесь 0 - своб. клетка, 1 - река, 2 и более - номера островов занимающих данные клетки
std::vector<std::vector<int>> mCodes; 
int n, m;
enum eCellStatus { FREE, RIVER, ISLAND };
std::vector<std::set<scoord>> vIslands;
 
// проверка выхода за пределы матрицы
bool insideMatrixBorders(coord_t p)
{
    return p.first >= 0 && p.first < mCodes.size() && p.second >= 0 && p.second < mCodes[0].size();
}
 
// проверяет валидно ли добавить клетку p к острову с номером islandNum
bool isValidCell(coord_t p, int islandNum)
{
    bool mb = insideMatrixBorders(p), ret = false;
    if (mb)
    {
        bool freeCell = mCodes[p.first][p.second] == 0;
        coord_t pp{ p.first - 1, p.second };
        bool cell1 = !insideMatrixBorders(pp) || mCodes[pp.first][pp.second] == FREE || mCodes[pp.first][pp.second] == islandNum;
        pp = { p.first + 1, p.second };
        bool cell2 = !insideMatrixBorders(pp) || mCodes[pp.first][pp.second] == FREE || mCodes[pp.first][pp.second] == islandNum;
        pp = { p.first, p.second - 1 };
        bool cell3 = !insideMatrixBorders(pp) || mCodes[pp.first][pp.second] == FREE || mCodes[pp.first][pp.second] == islandNum;
        pp = { p.first, p.second + 1 };
        bool cell4 = !insideMatrixBorders(pp) || mCodes[pp.first][pp.second] == FREE || mCodes[pp.first][pp.second] == islandNum;
        ret = mb && freeCell && cell1 && cell2 && cell3 && cell4;
    }
    return ret;
}
 
// возвращает список клеток которые можно добавить к клетке p
vcoord addedCells(coord_t p)
{
    vcoord vret;
    for (auto dlt : { 1, -1 })
    {
        if (coord_t pret = std::make_pair(p.first + dlt, p.second); isValidCell(pret, mCodes[p.first][p.second]))
        {
            vret.emplace_back(pret);
        }
        if (coord_t pret = std::make_pair(p.first, p.second + dlt); isValidCell(pret, mCodes[p.first][p.second]))
        {
            vret.emplace_back(pret);
        }
    }
    return vret;
}
 
// для координаты p в исходной матрице mtx находит все возможные варианты островов
std::set<scoord> islandVariants(coord_t p)
{
    int const islandNumber = mCodes[p.first][p.second];
    std::set<scoord> sret{ scoord{p} }, stmp;
    int num = mtx[p.first][p.second];
    for (int i = 0; i < num - 1; ++i)
    {
        for (auto& s : sret)
        {
            rng::for_each(s, [&p](auto& pp) { mCodes[pp.first][pp.second] = mCodes[p.first][p.second]; });
            for (auto& pp : s)
            {
                auto v = addedCells(pp);
                for (auto& ppp : v)
                {
                    scoord st = s;
                    st.emplace(ppp);
                    stmp.emplace(st);
                }
            }
            rng::for_each(s, [](auto& pp) { mCodes[pp.first][pp.second] = FREE; });
            mCodes[p.first][p.second] = islandNumber;
        }
        sret = stmp;
        stmp.clear();
    }
 
    return sret;
}
 
std::vector<std::set<scoord>::iterator> vres;
std::vector<std::vector<int>> mMap;
scoord sUsed;
 
// проверка реки на непрерывность обходом в ширину
bool bfs()
{
    bool bret = true;
    sUsed.clear();
    std::queue<coord_t> que;
    coord_t start;
    for (int i = 0; i < mMap.size(); ++i)
    {
        if (auto it = rng::find(mMap[i], RIVER); it != mMap[i].end())
        {
            start = { i, it - mMap[i].begin() };
            break;
        }
    }
    que.push(start);
    while (!que.empty())
    {
        coord_t p = que.front();
        que.pop();
        sUsed.insert(p);
        coord_t pp{ p.first - 1, p.second };
        if (insideMatrixBorders(pp) && mMap[pp.first][pp.second] == RIVER && !sUsed.contains(pp))
        {
            que.push(pp);
        }
        pp = { p.first + 1, p.second };
        if (insideMatrixBorders(pp) && mMap[pp.first][pp.second] == RIVER && !sUsed.contains(pp))
        {
            que.push(pp);
        }
        pp = { p.first, p.second - 1 };
        if (insideMatrixBorders(pp) && mMap[pp.first][pp.second] == RIVER && !sUsed.contains(pp))
        {
            que.push(pp);
        }
        pp = { p.first, p.second + 1 };
        if (insideMatrixBorders(pp) && mMap[pp.first][pp.second] == RIVER && !sUsed.contains(pp))
        {
            que.push(pp);
        }
    }
    for (int i = 0; i < mMap.size(); ++i)
    {
        for (int j = 0; j < mMap[i].size(); ++j)
        {
            if (mMap[i][j] == RIVER && !sUsed.contains({ i, j }))
            {
                bret = false;
                goto retMark;
            }
        }
    }
retMark: {}
    return bret;
}
 
// проверка реки на < 2x2 и непрерывность
bool validateRiver()
{
    bool bret = true;
    mMap.assign(n, std::vector<int>(m, RIVER));
    for (auto it : vres)
    {
        for (coord_t const& p : *it)
        {
            mMap[p.first][p.second] = ISLAND;
        }
    }
 
    // проверка на < 2x2
    for (int i = 0; i < mMap.size() - 1; ++i)
    {
        for (int j = 0; j < mMap[i].size() - 1; ++j)
        {
            if (mMap[i][j] == RIVER && mMap[i][j + 1] == RIVER && mMap[i + 1][j] == RIVER && mMap[i + 1][j + 1] == RIVER)
            {
                bret = false;
                goto retMark;
            }
        }
    }
 
    // проверка реки на непрерывность
    bret = bret && bfs();
 
retMark: {}
    return bret;
}
 
// проверяет пересечение последнего острова из vres со всеми предыдущими
bool intersect()
{
    bool bret = false;
    scoord const& scBack = *vres.back();
    for (int i = 0; i < vres.size() - 1; ++i)
    {
        scoord const& sc = *vres[i];
        for (auto& pBack : scBack)
        {
            for (auto& p : sc)
            {
                if (((pBack.first == p.first) && std::abs(pBack.second - p.second) == 1)
                    || ((pBack.second == p.second) && std::abs(pBack.first - p.first) == 1))
                {
                    bret = true;
                    goto retMark;
                }
            }
        }
    }
retMark: {}
    return bret;
}
 
// печатает остров
void printIsland(scoord const& sc)
{
    for (auto& p : sc)
    {
        std::cout << "(" << p.first << "," << p.second << ")";
    }
    std::cout << "\n";
}
 
// перебором находит все правильные карты
void bruteMaps(int ind = 0)
{
    if (ind == vIslands.size())
    {
        //std::cout << "intersect_ok  ";
        if (validateRiver())
        {
            std::cout << "map found:\n"; // карта найдена, печатаем все её острова
            for (auto it : vres)
            {
                printIsland(*it);
            }
            std::cout << "\n";
        }
    }
    else
    {
        for (auto ib = vIslands[ind].begin(); ib != vIslands[ind].end(); ++ib)
        {
            vres.push_back(ib);
            if (!intersect())
            {
                bruteMaps(ind + 1);
            }
            vres.pop_back();
        }
    }
}
 
int main() 
{
    // заполняем исходную матрицу mtx и вспомогательную матрицу mCodes
    n = 10, m = 10; // размер карты
    mtx.resize(n);
    rng::for_each(mtx, [](auto& v) { v.resize(m, 0); });
    std::vector<std::pair<coord_t, int>> vIslandsInit // координаты островов и их размеры
    { 
        {{0, 0}, 4}, 
        {{0, 4}, 2},
        {{0, 8}, 3},
        {{2, 0}, 3},
        {{2, 4}, 4},
        {{2, 8}, 2},
        {{4, 4}, 4},
        {{4, 8}, 3},
        {{5, 1}, 2},
        {{5, 5}, 4},
        {{7, 1}, 1},
        {{7, 5}, 2},
        {{7, 9}, 2},
        {{9, 1}, 4},
        {{9, 5}, 3},
        {{9, 9}, 3},
    };
    mCodes.resize(n);
    rng::for_each(mCodes, [](auto& v) { v.resize(m, FREE); });
    int islandNumber = ISLAND;
    for (auto& [p, islandSize] : vIslandsInit)
    {
        mCodes[p.first][p.second] = islandNumber;
        ++islandNumber;
        mtx[p.first][p.second] = islandSize;
    }
 
    // для каждой ненулевой ячейки матрицы mtx находим варианты островов
    for (int i = 0; i < mtx.size(); ++i)
    {
        for (int j = 0; j < mtx[i].size(); ++j)
        {
            if (mtx[i][j])
            {
                std::set<scoord> sres = islandVariants({ i, j });
                vIslands.push_back(sres);
                /* // найденные варианты для ячейки i, j
                std::cout << "(" << i << "," << j << ") " << sres.size() << "\n";
                for (auto& s : sres)
                {
                    printIsland(s);
                }
                std::cout << "\n";
                */
            }
        }
    }
 
    // находим все правильные карты
    bruteMaps();
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <cmath>
#include <iterator>
#include <queue>
#include <thread>
#include <mutex>
#include <atomic>
#include <chrono>
 
 
using coord_t = std::pair<int, int>; // координата в матрице: {row, column}
using vc_t = std::vector<coord_t>;
using sc_t = std::set<coord_t>;
 
// исходная матрица 
std::vector<std::vector<int>> mtx;
// вспомогательная матрица. Здесь 0 - своб. клетка, 1 - река, 2 и более - номера островов занимающих данные клетки
std::vector<std::vector<int>> mCodes;
int n, m;
enum eCellStatus { FREE, RIVER, ISLAND };
std::vector<std::set<sc_t>> vIslands;
 
 
// проверка выхода за пределы матрицы
bool insideMatrixBorders(coord_t p)
{
    return p.first >= 0 && p.first < mCodes.size() && p.second >= 0 && p.second < mCodes[0].size();
}
 
// проверяет валидно ли добавить клетку p к острову с номером islandNum
bool isValidCell(coord_t p, int islandNum)
{
    bool mb = insideMatrixBorders(p), ret = false;
    if (mb)
    {
        bool freeCell = mCodes[p.first][p.second] == 0;
        coord_t pp{ p.first - 1, p.second };
        bool cell1 = !insideMatrixBorders(pp) || mCodes[pp.first][pp.second] == FREE || mCodes[pp.first][pp.second] == islandNum;
        pp = { p.first + 1, p.second };
        bool cell2 = !insideMatrixBorders(pp) || mCodes[pp.first][pp.second] == FREE || mCodes[pp.first][pp.second] == islandNum;
        pp = { p.first, p.second - 1 };
        bool cell3 = !insideMatrixBorders(pp) || mCodes[pp.first][pp.second] == FREE || mCodes[pp.first][pp.second] == islandNum;
        pp = { p.first, p.second + 1 };
        bool cell4 = !insideMatrixBorders(pp) || mCodes[pp.first][pp.second] == FREE || mCodes[pp.first][pp.second] == islandNum;
        ret = mb && freeCell && cell1 && cell2 && cell3 && cell4;
    }
    return ret;
}
 
// возвращает список клеток которые можно добавить к клетке p
vc_t addedCells(coord_t p)
{
    vc_t vret;
    for (auto dlt : { 1, -1 })
    {
        if (coord_t pret = std::make_pair(p.first + dlt, p.second); isValidCell(pret, mCodes[p.first][p.second]))
        {
            vret.emplace_back(pret);
        }
        if (coord_t pret = std::make_pair(p.first, p.second + dlt); isValidCell(pret, mCodes[p.first][p.second]))
        {
            vret.emplace_back(pret);
        }
    }
    return vret;
}
 
// для координаты p в исходной матрице mtx находит все возможные варианты островов
std::set<sc_t> islandVariants(coord_t p)
{
    int const islandNumber = mCodes[p.first][p.second];
    std::set<sc_t> sret{ sc_t{p} }, stmp;
    int num = mtx[p.first][p.second];
    for (int i = 0; i < num - 1; ++i)
    {
        for (auto const& s : sret)
        {
            std::for_each(s.begin(), s.end(), [&p](auto& pp) { mCodes[pp.first][pp.second] = mCodes[p.first][p.second]; });
            for (auto& pp : s)
            {
                auto const v = addedCells(pp);
                for (auto& ppp : v)
                {
                    sc_t st = s;
                    st.emplace(ppp);
                    stmp.emplace(st);
                }
            }
            std::for_each(s.begin(), s.end(), [](auto const& pp) { mCodes[pp.first][pp.second] = FREE; });
            mCodes[p.first][p.second] = islandNumber;
        }
        sret = stmp;
        stmp.clear();
    }
 
    return sret;
}
 
std::vector<std::vector<std::set<sc_t>::iterator>> mRes;
std::vector <std::vector<std::vector<int>>> mMap;
std::vector<sc_t> sUsed;
 
// проверка реки на непрерывность обходом в ширину
bool bfs(int indThread)
{
    bool bret = true;
    auto& mMapRef = mMap[indThread];
    auto& sUsedRef = sUsed[indThread];
    sUsedRef.clear();
    std::queue<coord_t> que;
    coord_t start;
    for (int i = 0; i < mMapRef.size(); ++i)
    {
        if (auto it = std::find(mMapRef[i].begin(), mMapRef[i].end(), RIVER); it != mMapRef[i].end())
        {
            start = { i, it - mMapRef[i].begin() };
            break;
        }
    }
    que.push(start);
    while (!que.empty())
    {
        coord_t p = que.front();
        que.pop();
        sUsedRef.insert(p);
        coord_t pp{ p.first - 1, p.second };
        if (insideMatrixBorders(pp) && mMapRef[pp.first][pp.second] == RIVER && !sUsedRef.contains(pp))
        {
            que.push(pp);
        }
        pp = { p.first + 1, p.second };
        if (insideMatrixBorders(pp) && mMapRef[pp.first][pp.second] == RIVER && !sUsedRef.contains(pp))
        {
            que.push(pp);
        }
        pp = { p.first, p.second - 1 };
        if (insideMatrixBorders(pp) && mMapRef[pp.first][pp.second] == RIVER && !sUsedRef.contains(pp))
        {
            que.push(pp);
        }
        pp = { p.first, p.second + 1 };
        if (insideMatrixBorders(pp) && mMapRef[pp.first][pp.second] == RIVER && !sUsedRef.contains(pp))
        {
            que.push(pp);
        }
    }
    for (int i = 0; i < mMapRef.size(); ++i)
    {
        for (int j = 0; j < mMapRef[i].size(); ++j)
        {
            if (mMapRef[i][j] == RIVER && !sUsedRef.contains({ i, j }))
            {
                bret = false;
                goto retMark;
            }
        }
    }
retMark: {}
    return bret;
}
 
// проверка реки на < 2x2 и непрерывность
bool validateRiver(int indThread)
{
    bool bret = true;
    auto& mMapRef = mMap[indThread];
    mMapRef.assign(n, std::vector<int>(m, RIVER));
    for (auto it : mRes[indThread])
    {
        for (coord_t const& p : *it)
        {
            mMapRef[p.first][p.second] = ISLAND;
        }
    }
 
    // проверка на < 2x2
    for (int i = 0; i < mMapRef.size() - 1; ++i)
    {
        for (int j = 0; j < mMapRef[i].size() - 1; ++j)
        {
            if (mMapRef[i][j] == RIVER && mMapRef[i][j + 1] == RIVER && mMapRef[i + 1][j] == RIVER && mMapRef[i + 1][j + 1] == RIVER)
            {
                bret = false;
                goto retMark;
            }
        }
    }
 
    // проверка реки на непрерывность
    bret = bret && bfs(indThread);
 
retMark: {}
    return bret;
}
 
// проверяет пересечение последнего острова из vres со всеми предыдущими
bool intersect(int indThread)
{
    bool bret = false;
    auto& mResRef = mRes[indThread];
    sc_t const& scBack = *mResRef.back();
    for (int i = 0; i < mResRef.size() - 1; ++i)
    {
        sc_t const& sc = *mResRef[i];
        for (auto& pBack : scBack)
        {
            for (auto& p : sc)
            {
                if (((pBack.first == p.first) && std::abs(pBack.second - p.second) == 1)
                    || ((pBack.second == p.second) && std::abs(pBack.first - p.first) == 1))
                {
                    bret = true;
                    goto retMark;
                }
            }
        }
    }
retMark: {}
    return bret;
}
 
// печатает остров
void printIsland(sc_t const& sc)
{
    for (auto& p : sc)
    {
        std::cout << "(" << p.first << "," << p.second << ")";
    }
    std::cout << "\n";
}
 
std::atomic_int ai;
std::mutex mxCout;
 
// перебором находит все правильные карты
void bruteMaps(int indThread, int indIsland = 0)
{
    auto& mResRef = mRes[indThread];
    if (indIsland == vIslands.size())
    {
        if (validateRiver(indThread))
        {
            // карта найдена, печатаем все её острова
            std::lock_guard lgCout{ mxCout };
            std::cout << "map found:\n";
            for (auto it : mResRef)
            {
                printIsland(*it);
            }
            std::cout << "\n";
        }
    }
    else
    {
        for (auto ib = vIslands[indIsland].cbegin(); ib != vIslands[indIsland].cend(); ++ib)
        {
            mResRef.push_back(ib);
            if (!intersect(indThread))
            {
                bruteMaps(indThread, indIsland + 1);
            }
            mResRef.pop_back();
        }
    }
}
 
int main()
{
    // входные данные
    n = 10, m = 10; // размер карты
    std::vector<std::pair<coord_t, int>> vIslandsInit // координаты островов и их размеры
    {
        {{0, 0}, 4},
        {{0, 4}, 2},
        {{0, 8}, 3},
        {{2, 0}, 3},
        {{2, 4}, 4},
        {{2, 8}, 2},
        {{4, 4}, 4},
        {{4, 8}, 3},
        {{5, 1}, 2},
        {{5, 5}, 4},
        {{7, 1}, 1},
        {{7, 5}, 2},
        {{7, 9}, 2},
        {{9, 1}, 4},
        {{9, 5}, 3},
        {{9, 9}, 3},
    };
 
    // заполняем исходную матрицу mtx и вспомогательную матрицу mCodes
    mtx.resize(n);
    std::for_each(mtx.begin(), mtx.end(), [](auto& v) { v.resize(m, 0); });
    mCodes.resize(n);
    std::for_each(mCodes.begin(), mCodes.end(), [](auto& v) { v.resize(m, FREE); });
    int islandNumber = ISLAND;
    for (auto const& [p, islandSize] : vIslandsInit)
    {
        mCodes[p.first][p.second] = islandNumber;
        ++islandNumber;
        mtx[p.first][p.second] = islandSize;
    }
 
    // для каждой ненулевой ячейки матрицы mtx находим варианты островов
    for (int i = 0; i < mtx.size(); ++i)
    {
        for (int j = 0; j < mtx[i].size(); ++j)
        {
            if (mtx[i][j])
            {
                std::set<sc_t> sres = islandVariants({ i, j });
                vIslands.push_back(sres);
            }
        }
    }
 
    // находим все правильные карты (ф-ция bruteMaps работает в несколько потоков)
    if(vIslands.size() < 2) // число островов на карте должно быть >= 2 т.к. параллелим на глубину 2
    {
        std::cerr << "vIslands.size() < 2\n";
        throw 1;
    }
    std::sort(vIslands.begin(), vIslands.end(), [](auto const& a, auto const& b) {return a.size() > b.size(); });
    ai = vIslands[0].size() * vIslands[1].size() - 1;
    std::vector<std::thread> vThreads;
    int cntThreads = std::thread::hardware_concurrency(); // число потоков
    mRes.resize(cntThreads);
    mMap.resize(cntThreads);
    sUsed.resize(cntThreads);
    auto tpStart = std::chrono::high_resolution_clock::now();
    for (int indThread = 0; indThread < cntThreads; ++indThread)
    {
        vThreads.emplace_back([indThread]()
            {
                while (true)
                {
                    int ind01 = ai--;
                    if (ind01 < 0)
                        break;
                    int ind0 = ind01 / vIslands[1].size();
                    int ind1 = ind01 % vIslands[1].size();
                    auto& mResRef = mRes[indThread];
                    mResRef.clear();
                    auto it0 = vIslands[0].cbegin();
                    std::advance(it0, ind0);
                    mResRef.emplace_back(it0);
                    auto it1 = vIslands[1].cbegin();
                    std::advance(it1, ind1);
                    mResRef.emplace_back(it1);
                    if (!intersect(indThread))
                    {
                        bruteMaps(indThread, 2);
                    }
                }
            });
    }
    std::for_each(vThreads.begin(), vThreads.end(), [](auto& t) { t.join(); });
    auto tpFinish = std::chrono::high_resolution_clock::now();
    std::cout << "time: " << std::chrono::duration_cast<std::chrono::milliseconds>(tpFinish - tpStart).count() << "\n";
}