Определите количество предметов, расположенных в помещении

@Pelmen342 · Регистрация: 05.04.2022

Студворк — интернет-сервис помощи студентам

Помогите пожалуйста. Задачу я решила, но мне пишет на двух тестах ошибка выполнения. Ограничение массива в условии задачи стоит 300, я пишу этот размер и пишет ошибка выполнения. Что делать?

Вот код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
int a[300][300];
 
int i, j, m, n, kol;
 
void rec(int x, int y){
 
    if (a[x][y] == 0) return;
 
    a[x][y] = 0;
 
    rec(x + 1, y);
    rec(x - 1, y);
    rec(x, y + 1);
    rec(x, y - 1);
}
 
int main(){
 
    cin >> n >> m;
 
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) cin >> a[i][j];
 
    kol = 0;
 
    for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++) if (a[i][j] == 1){
 
        kol++;
 
        rec(i, j);
    }
 
    cout << kol << endl;
 
    return 0;
}

@TheCalligrapher · 13.09.2022, 06:43

Сообщение от John Prick

Подумайте, что будет, когда вы в эту функцию передадите граничные индексы.

По первому варианту кода ясно видно, что ненулевыми данными автор планировал заполнять ячейки массива с индексами 1 и более

C++
1
2
      for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) cin >> a[i][j];

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

C++
1
if (a[x][y] == 0) return;

И это красиво.

Конечно же, для корректной реализации этой идеи, массив должен иметь размер "на 2 больше" в обоих измерениях. То есть в первом варианте кода нужен массив [302][302].

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

C++
1
unsigned char a[302][302];

Готово.

В переписанном же "динамическом" варианте кода автор зачем-то умудрился угробить эту весьма разумную задумку. В результате появились проблемы с краевыми индексами. Зачем было городить весь этот огород?

--

Решать такую задачу голым графовым поиском - странная затея. Однако если вы уж собрались это делать, то разумнее использовать поиск в ширину, а не поиск в глубину. Поиск в глубину на "плохих" входах приведет к неоправданно высокой глубине рекурсии.

Однако намного разумнее было бы просто пройти по всей матрице и поcчитать угловые точки вида

Code
1
2
0 0
0 1

Это и есть количество предметов. И не надо никакого графового поиска...

@Pelmen342 · 13.09.2022, 17:11 **[ТС]**

А можете пожалуйста примерный код прислать?

Добавлено через 27 минут
Или можно пожалуйста решение этой задачи без рекурсии?

Добавлено через 26 минут
Ещё мне говорили что нужно сохранять две строки если элемент равен предыдущему по i и j. Как это можно сделать?

@TheCalligrapher · 13.09.2022, 22:41

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cassert>
#include <iostream>
 
int main()
{
  unsigned n = 0, m = 0;
  std::cin >> n >> m;
  assert(n <= 300 && m <= 300);
 
  bool a[301][301] = {};
  
  for (unsigned i = 1; i <= n; ++i)
    for (unsigned j = 1; j <= m; ++j) 
      std::cin >> a[i][j];
 
  unsigned kol = 0;
 
  for (unsigned i = 1; i <= n; ++i)
    for (unsigned j = 1; j <= m; ++j) 
      if (a[i][j] && !a[i - 1][j] && !a[i][j - 1])
        ++kol;
 
  std::cout << kol << std::endl;
}

Разумеется, в таком варианте все это можно существенно компактизировать по памяти

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cassert>
#include <utility>
#include <iostream>
 
int main()
{
  unsigned n = 0, m = 0;
  std::cin >> n >> m;
  assert(m <= 300);
 
  bool mem[2][301] = {}, *a[2] = { mem[0], mem[1] };
  
  unsigned kol = 0;
  
  for (unsigned i = 1; i <= n; ++i, std::swap(a[0], a[1]))
    for (unsigned j = 1; j <= m; ++j) 
    {
      std::cin >> a[1][j];
      if (a[1][j] && !a[0][j] && !a[1][j - 1])
        ++kol;
    }
  
  std::cout << kol << std::endl;
}

А можно обойтись и одной строкой bool a[301];...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cassert>
#include <iostream>
 
int main()
{
  unsigned n = 0, m = 0;
  std::cin >> n >> m;
  assert(m <= 300);
 
  bool a[301] = {};
  
  unsigned kol = 0;
  
  for (unsigned i = 1; i <= n; ++i)
    for (unsigned j = 1; j <= m; ++j) 
    {
      bool v = false;
      std::cin >> v;
      
      if (v && !a[j - 1] && !a[j])
        ++kol;
        
      a[j] = v;
    }
  
  std::cout << kol << std::endl;
}

@Pelmen342 · 13.09.2022, 22:52 **[ТС]**

TheCalligrapher, спасибо за помощь)

Новые блоги и статьи Все статьи Все блоги /
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@Pelmen342 1 / 1 / 0 Регистрация: 05.04.2022 Сообщений: 52
	13.09.2022, 17:11 [ТС]
	А можете пожалуйста примерный код прислать? Добавлено через 27 минут Или можно пожалуйста решение этой задачи без рекурсии? Добавлено через 26 минут Ещё мне говорили что нужно сохранять две строки если элемент равен предыдущему по i и j. Как это можно сделать? 0

@Pelmen342 1 / 1 / 0 Регистрация: 05.04.2022 Сообщений: 52
	13.09.2022, 22:52 [ТС]
	TheCalligrapher, спасибо за помощь) 0

Определите количество предметов, расположенных в помещении

Решение