Есть матрица чисел размерности MxN. Все эелементы заполнены единицами. Из матрицы удалили P элементов (т.е. каждый P[i,j] заменили на 0). Надо выяснить, на сколько частей в результате разбилась матрица.

Например,

до:

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

после:

0 0 1 1
0 1 0 0
1 0 0 1
0 1 1 0

// получили разбиение на 5 частей

Здравствуйте, C0nsul, Вы писали:

C>Есть матрица чисел размерности MxN. Все эелементы заполнены единицами. Из матрицы удалили P элементов (т.е. каждый P[i,j] заменили на 0). Надо выяснить, на сколько частей в результате разбилась матрица.

Вариант решения:
1. Пишешь структуру для хранения каждой части.....
(массив точек, по крайним точками,.....)
2. Построчно, а в строках — поэлементно анализируешь свою матрицу. Если 0 — ничего, если 1 — то смотришь, не добавляется ли эта единица к существующим частям, да — добавляешь, нет — образуешь новую часть...Не забыдь про возможность объединения двух частей...

С учетом всего получится O(MxN)

Здравствуйте, C0nsul, Вы писали:

C>Есть матрица чисел размерности MxN. Все эелементы заполнены единицами. Из матрицы удалили P элементов (т.е. каждый P[i,j] заменили на 0). Надо выяснить, на сколько частей в результате разбилась матрица.

C>Например,

C>до:

C>1 1 1 1
C>1 1 1 1
C>1 1 1 1
C>1 1 1 1

C>после:

C>0 0 1 1
C>0 1 0 0
C>1 0 0 1
C>0 1 1 0

C>// получили разбиение на 5 частей

Подсчет количества компонент связности с помощью поиска в ширину.

Здравствуйте, C0nsul, Вы писали:

C>Есть матрица чисел размерности MxN. Все эелементы заполнены единицами. Из матрицы удалили P элементов (т.е. каждый P[i,j] заменили на 0). Надо выяснить, на сколько частей в результате разбилась матрица.

C>Например,

C>до:

C>1 1 1 1
C>1 1 1 1
C>1 1 1 1
C>1 1 1 1

C>после:

C>0 0 1 1
C>0 1 0 0
C>1 0 0 1
C>0 1 1 0

C>// получили разбиение на 5 частей

Самый простой алгоритм заливки

char matrix[100][100];
int segments = 0;

void fill(int matrix[100][100], int i, int j) {
   if (matrix[i][j] == 1) {
      matrix[i][j] = 0;
      // проверку на выход за пределы, или дополнительные строки и столбцы по краям, состоящие из нулей.
      fill(matrix, i-1, j);
      fill(matrix, i+1, j);
      fill(matrix, i, j-1);
      fill(matrix, i, j+1);
   }
}

for (int i=0; i<100; ++i)
   for (int j=0; j<100; ++j)
      if (matrix[i][j] == 1) {
         ++segments;
         fill(matrix, i, j);
      }

Здравствуйте, C0nsul, Вы писали:

C>Есть матрица чисел размерности MxN. Все эелементы заполнены единицами. Из матрицы удалили P элементов (т.е. каждый P[i,j] заменили на 0). Надо выяснить, на сколько частей в результате разбилась матрица.

C>Например,

C>до:

C>1 1 1 1
C>1 1 1 1
C>1 1 1 1
C>1 1 1 1

C>после:

C>0 0 1 1
C>0 1 0 0
C>1 0 0 1
C>0 1 1 0

C>// получили разбиение на 5 частей

Выделяешь еще один массив для такой же по размеру матрицы:
В ней будем проставлять по порядку 1, 2, 3 ... и т.д номер части

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

Алгоритм правда памяти требует, но зато быстро O(N)

Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Здравствуйте, C0nsul, Вы писали:

C>>Есть матрица чисел размерности MxN. Все эелементы заполнены единицами. Из матрицы удалили P элементов (т.е. каждый P[i,j] заменили на 0). Надо выяснить, на сколько частей в результате разбилась матрица.

C>>Например,

C>>до:

C>>1 1 1 1
C>>1 1 1 1
C>>1 1 1 1
C>>1 1 1 1

C>>после:

C>>0 0 1 1
C>>0 1 0 0
C>>1 0 0 1
C>>0 1 1 0

C>>// получили разбиение на 5 частей

ATP>Выделяешь еще один массив для такой же по размеру матрицы:
ATP>В ней будем проставлять по порядку 1, 2, 3 ... и т.д номер части

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

Не будет работать на следующем примере:
1111
0001
1111
0001
1111

Матрица вторая будет

1111
0001
222?
000?
333?

ATP>Алгоритм правда памяти требует, но зато быстро O(N)
Размерность матрицы уже N*M

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>>Здравствуйте, C0nsul, Вы писали:

C>>>Есть матрица чисел размерности MxN. Все эелементы заполнены единицами. Из матрицы удалили P элементов (т.е. каждый P[i,j] заменили на 0). Надо выяснить, на сколько частей в результате разбилась матрица.

C>>>Например,

C>>>до:

C>>>1 1 1 1
C>>>1 1 1 1
C>>>1 1 1 1
C>>>1 1 1 1

C>>>после:

C>>>0 0 1 1
C>>>0 1 0 0
C>>>1 0 0 1
C>>>0 1 1 0

C>>>// получили разбиение на 5 частей

ATP>>Выделяешь еще один массив для такой же по размеру матрицы:
ATP>>В ней будем проставлять по порядку 1, 2, 3 ... и т.д номер части

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

_DA>Не будет работать на следующем примере:
_DA>1111
_DA>0001
_DA>1111
_DA>0001
_DA>1111

_DA>Матрица вторая будет

_DA>1111
_DA>0001
_DA>222?
_DA>000?
_DA>333?

ATP>>Алгоритм правда памяти требует, но зато быстро O(N)
_DA>Размерность матрицы уже N*M

Действительно — сорри!
Значит каждая строка по два прохода, в первом ставить номер только если есть область наверху, во втором то, что я уже описал. Итак по 2 раза для каждой строки — всеравно O (N)

Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>Здравствуйте, _DAle_, Вы писали:

_DA>>Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>>>Здравствуйте, C0nsul, Вы писали:

C>>>>Есть матрица чисел размерности MxN. Все эелементы заполнены единицами. Из матрицы удалили P элементов (т.е. каждый P[i,j] заменили на 0). Надо выяснить, на сколько частей в результате разбилась матрица.

C>>>>Например,

C>>>>до:

C>>>>1 1 1 1
C>>>>1 1 1 1
C>>>>1 1 1 1
C>>>>1 1 1 1

C>>>>после:

C>>>>0 0 1 1
C>>>>0 1 0 0
C>>>>1 0 0 1
C>>>>0 1 1 0

C>>>>// получили разбиение на 5 частей

ATP>>>Выделяешь еще один массив для такой же по размеру матрицы:
ATP>>>В ней будем проставлять по порядку 1, 2, 3 ... и т.д номер части

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

_DA>>Не будет работать на следующем примере:
_DA>>1111
_DA>>0001
_DA>>1111
_DA>>0001
_DA>>1111

_DA>>Матрица вторая будет

_DA>>1111
_DA>>0001
_DA>>222?
_DA>>000?
_DA>>333?

ATP>>>Алгоритм правда памяти требует, но зато быстро O(N)
_DA>>Размерность матрицы уже N*M

ATP>Действительно — сорри!
ATP>Значит каждая строка по два прохода, в первом ставить номер только если есть область наверху, во втором то, что я уже описал. Итак по 2 раза для каждой строки — всеравно O (N)

Опять сорри! Видимо без рекурсии не обойтись...

Здравствуйте, AcidTheProgrammer, Вы писали:


ATP>>Действительно — сорри!
ATP>>Значит каждая строка по два прохода, в первом ставить номер только если есть область наверху, во втором то, что я уже описал. Итак по 2 раза для каждой строки — всеравно O (N)

ATP>Опять сорри! Видимо без рекурсии не обойтись...

Здесь нужен просто обход графа, и не важно будет ли это поиск в глубину или поиск в ширину, и так же не важно, будет ли это реализовано с помощью рекурсии или с использованием очереди...
А сложность будет O(N*M).

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, AcidTheProgrammer, Вы писали:

ATP>>Здравствуйте, C0nsul, Вы писали:

C>>>Есть матрица чисел размерности MxN. Все эелементы заполнены единицами. Из матрицы удалили P элементов (т.е. каждый P[i,j] заменили на 0). Надо выяснить, на сколько частей в результате разбилась матрица.

C>>>Например,

C>>>до:

C>>>1 1 1 1
C>>>1 1 1 1
C>>>1 1 1 1
C>>>1 1 1 1

C>>>после:

C>>>0 0 1 1
C>>>0 1 0 0
C>>>1 0 0 1
C>>>0 1 1 0

C>>>// получили разбиение на 5 частей

ATP>>Выделяешь еще один массив для такой же по размеру матрицы:
ATP>>В ней будем проставлять по порядку 1, 2, 3 ... и т.д номер части

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

_DA>Не будет работать на следующем примере:
_DA>1111
_DA>0001
_DA>1111
_DA>0001
_DA>1111

_DA>Матрица вторая будет

_DA>1111
_DA>0001
_DA>222?
_DA>000?
_DA>333?

ATP>>Алгоритм правда памяти требует, но зато быстро O(N)
_DA>Размерность матрицы уже N*M

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

Тогда после:
1111
0001
222?
000?
333?

будет

1111
0001
1111
0001
222?

и

1111
0001
1111
0001
1111

Всеравно O (N).

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, AcidTheProgrammer, Вы писали:


ATP>>>Действительно — сорри!
ATP>>>Значит каждая строка по два прохода, в первом ставить номер только если есть область наверху, во втором то, что я уже описал. Итак по 2 раза для каждой строки — всеравно O (N)

ATP>>Опять сорри! Видимо без рекурсии не обойтись...

_DA>Здесь нужен просто обход графа, и не важно будет ли это поиск в глубину или поиск в ширину, и так же не важно, будет ли это реализовано с помощью рекурсии или с использованием очереди...
_DA>А сложность будет O(N*M).

Посмотрите следующую мою поправку, вроде нет никакихх графов?

Здравствуйте, AcidTheProgrammer, Вы писали:


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

ATP>Тогда после:
ATP>1111
ATP>0001
ATP>222?
ATP>000?
ATP>333?

ATP>будет

ATP>1111
ATP>0001
ATP>1111
ATP>0001
ATP>222?

ATP>и

ATP>1111
ATP>0001
ATP>1111
ATP>0001
ATP>1111

ATP>Всеравно O (N).

Хех. Пойдем на крайние меры убеждения. Спиральки порисуем.
Тест 1.
1111111
0000001
1111101
1000101
1011101
1000001
1111111
Тест 2.
1111111
1000000
1011111
1010001
1011101
1000001
1111111

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, AcidTheProgrammer, Вы писали:


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

ATP>>Тогда после:
ATP>>1111
ATP>>0001
ATP>>222?
ATP>>000?
ATP>>333?

ATP>>будет

ATP>>1111
ATP>>0001
ATP>>1111
ATP>>0001
ATP>>222?

ATP>>и

ATP>>1111
ATP>>0001
ATP>>1111
ATP>>0001
ATP>>1111

ATP>>Всеравно O (N).

_DA> Хех. Пойдем на крайние меры убеждения. Спиральки порисуем.
_DA>Тест 1.
_DA>1111111
_DA>0000001
_DA>1111101
_DA>1000101
_DA>1011101
_DA>1000001
_DA>1111111
_DA>Тест 2.
_DA>1111111
_DA>1000000
_DA>1011111
_DA>1010001
_DA>1011101
_DA>1000001
_DA>1111111

— ой спасибо — настроение поднялость!!!! А я и не знал что я такой оптимист...
Все — понял, дейсвительно без графа не обойтись, убедили!!!