Как проверить, на сколько частей делится матрица

Question

У меня есть матрица из нулей и единиц. Мне нужен способ увидеть, сколько "нулевых блоков" существует. Вот картинка, чтобы лучше проиллюстрировать:

В этом примере 4 "нулевых блока", разделенных на черные блоки (единицы в матрице).

Answer 1

Как уже упоминалось выше, вы можете использовать dfs для поиска компонентов на графике. Вот пример кода classi c, работающий с сеткой, где X означает стену, а 0 означает свободное пространство (в вашем случае черные и белые квадраты):

#include <vector>
#include <string>

using Map = std::vector<std::string>;
using BoolMap = std::vector<std::vector<bool>>;

void dfs(BoolMap& visited, int x, int y)
{
    if (x < 0 || y < 0 || y >= visited.size() || x >= visited[y].size())
        return;
    if (visited[y][x]) 
        return;

    visited[y][x] = true;
    dfs(visited, x - 1, y);
    dfs(visited, x + 1, y);
    dfs(visited, x, y - 1);
    dfs(visited, x, y + 1);
}

int main()
{
    Map map;
    map.emplace_back("0X00");
    map.emplace_back("XXX0");
    map.emplace_back("0X0X");
    map.emplace_back("0X00");

    BoolMap visited(map.size());
    for (size_t y = 0; y < map.size(); y++)
    {
        visited[y].resize(map[y].size());
        for (size_t x = 0; x < map[y].size(); x++)
        {
            // set visited to true if there is a wall
            visited[y][x] = (map[y][x] == 'X');
        }
   }

    size_t component_count = 0;

    for (size_t y = 0; y < map.size(); y++)
    {
         for (size_t x = 0; x < map[y].size(); x++)
        {
            if (!visited[y][x])
            {
                dfs(visited, x, y);
                component_count++;
            }
        }
    }

    std::cout << component_count << std::endl;
}

Этот код может быть проще, если вы знаете что ваша карта всегда квадратная (map.size () можно использовать вместо map [y] .size ()). Также я дважды просматриваю карту, чтобы проверить стены, но если она не слишком велика, проблем с производительностью не должно быть.

Если вы уже работаете с булевой матрицей, и это нормально изменив его, вы можете просто передать его в качестве параметра посещения, и алгоритм будет работать так же.

Answer 2

Я рекомендую взглянуть на BFS и DFS для обхода графа. Вы можете представить свою матрицу в виде графика, где каждая ячейка связана со своими соседями в 4 направлениях: север, юг, восток и запад.

Если у вас есть проблема, дайте мне знать в комментариях для получения более подробной информации .