Здравствуйте, 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 частей

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

Здравствуйте, 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

Есть матрица чисел размерности 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 частей

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

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).

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

Здравствуйте, _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

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