Почему моя программа выдает ошибку времени выполнения после удаления комментариев в приведенном ниже коде?

Есть поле с растениями — сетка из N строк (пронумерованных от 1 до N) и M столбцов (пронумерованных от 1 до M); из его клеток NM K-клетки содержат растения, а остальные - сорняки. За пределами этой сетки везде сорняки. Две клетки являются смежными, если они имеют общую сторону.

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

из этой клетки можно перемещаться в каждую соседнюю ячейку с растением, не пересекая никаких заборов невозможно перейти из этой клетки в любую клетку с сорняками, не пересекая никаких заборов

Вход:

Первая строка входных данных содержит единственное целое число T, обозначающее количество тестовых случаев. Ниже приводится описание T тестовых случаев. Первая строка каждого набора входных данных содержит три целых числа через пробел N, M и K. Далее идут K строк. Каждая из этих строк содержит два целых числа r и c, разделенных пробелами, обозначающих, что в ячейке строки r и столбца c находится растение.

#include <iostream>
#include<vector>
#include<queue>
using namespace std;

int main() {
    // your code goes here
    int t,n,m,i,j,k,flag=0;
    int r[4] = {-1,1,0,0};
    int c[4] = {0,0,-1,1};
    cin>>t;
    while(t--) {
        int ans=0;
        cin>>n>>m>>k;
      vector < vector<int> >  vec(n, vector<int>(m,0));

      /* for(int z=0; z<k; z++) {
            cin>>i>>j;
            vec[i-1][j-1] = 1;
        } */
        queue<pair<int,int>> q;
        for(i=0;i<n;i++) {
            for(j=0;j<m;j++) {
                if (vec[i][j] == 1) {
                    q.push(make_pair(i,j));
                    flag = 1;
                    break;
                }
            }
            if (flag==1)
            break;
        }
        while(!q.empty()) {
            pair<int,int> p = q.front();
            int a = p.first;
            int b = p.second;
          int x=0;
            q.pop();
            for(i=0;i<4;i++) {
                for(j=0;j<4;j++) {
                    int rr = a + r[i];
                    int cc = b + c[j];
                    if (rr<0 || cc<0 || rr>=n || cc>=m || vec[rr][cc]==0)
                    continue;
                    else {
                        q.push(make_pair(rr,cc));
                        x++;
                    }
                }
            }
            ans = ans + (4-x);
        }
         cout<<ans<<endl;

    }
    return 0;
}

Если я удалю комментарии выше, это покажет ошибку тайм-аута. Я не могу обнаружить проблему с приведенным выше утверждением.

вы, кажется, используете i и j для входов r и c и определяете r и c в начале. Зачем?

Tzalumen 09.04.2019 17:22

Короткий ответ - это то, что сказал другой человек: ваш алгоритм работает слишком долго. Он переполняется, когда вы удаляете закомментированные строки, потому что это строки, заполняющие вашу векторную матрицу, а ваш алгоритм не работает с незаполненной матрицей (как и следовало ожидать).

Tzalumen 09.04.2019 17:26

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

François Andrieux 09.04.2019 17:26

@FrançoisAndrieux Я узнаю этот стиль, в закомментированном разделе используется тестовый ввод. Это похоже на проблему с HackerRank или подобного сайта.

Tzalumen 09.04.2019 17:27

Кроме того, Никита, тайм-аут — это не ошибка времени выполнения, это состояние сбоя на любом сайте испытаний, на котором вы находитесь, что указывает на то, что ваше решение решает проблему слишком медленно. Ваш код может компилироваться и работать и быть совершенно стабильным юридическим кодом, который правильно решает проблему, но он слишком медленный для вашей задачи. Я собираюсь догадаться, потому что на основе вложенности вашего цикла это выглядит как O (n ^ 3) или O (n ^ 4).

Tzalumen 09.04.2019 17:31

@Никита, поведение сильно зависит от ввода. Предоставьте (упрощенный) ввод, который приводит к тайм-ауту.

nVxx 09.04.2019 18:14

Хорошая практика: всегда проверяйте правильность ввода пользователя (также проверяйте состояние потока!). Вы обходите довольно много проблем, если пользователь вводит что-то недопустимое...

Aconcagua 09.04.2019 18:22

О используя пространство имен std...

Aconcagua 09.04.2019 18:22

Флаг, необходимый для выхода из вложенного цикла, довольно уродлив. Это был бы один из (довольно немногих) случаев, когда использование goto было бы допустимым. Лямбда returning из вложенного цикла является альтернативой...

Aconcagua 09.04.2019 18:53

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

Aconcagua 09.04.2019 18:59
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
10
342
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Предположим, что пользователь установил 1 для обеих пар (6, 7) и (7, 7).

Тогда произойдет следующее:

  • первая обнаруженная пара будет (6, 7)
  • для пары (6, 7) в очередь будет добавлена ​​пара (7, 7)
  • для пары (7, 7) снова будет добавлена ​​пара (6, 7) (но ранее она была удалена)
  • для пары (6, 7) снова будет добавлена ​​пара (7, 7)
  • ...

Таким образом, ваш цикл никогда не завершится, если есть только одна пара соседних пар (и проблема будет хуже с большими группами).

Если вы хотите избежать этого, вы можете установить vec[rr][cc] = 0 после посещения поля; в качестве альтернативы вы можете установить vec[rr][cc] = -1 (или любое другое значение, отличное от 0 и 1), тогда вы сможете различать: 1, не посещенный 0 (но с тем же значением), посещенный 0 (измененный на -1). Однако вам нужно настроить чек:

if (0 <= rr && rr < n && 0 <= cc && cc < m && vec[rr][cc] == 1)
// ...

потому что пропустить == 0 уже не получится (переупорядочивать сравнения не нужно, но в том виде, в котором они есть сейчас, это больше похоже на математическое уравнение 0 <= rr <= n, которое, конечно, нельзя так записать на C++).

Другие вопросы по теме