Есть поле с растениями — сетка из 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;
}
Если я удалю комментарии выше, это покажет ошибку тайм-аута. Я не могу обнаружить проблему с приведенным выше утверждением.
Короткий ответ - это то, что сказал другой человек: ваш алгоритм работает слишком долго. Он переполняется, когда вы удаляете закомментированные строки, потому что это строки, заполняющие вашу векторную матрицу, а ваш алгоритм не работает с незаполненной матрицей (как и следовало ожидать).
Раздел с комментариями ожидает ввода данных пользователем. Так что интерфейс вашей программы совсем другой. Если вы не скорректируете ввод соответствующим образом, поведение будет отличаться от обычного. Если вход является отличается, неясно, что это за ввод.
@FrançoisAndrieux Я узнаю этот стиль, в закомментированном разделе используется тестовый ввод. Это похоже на проблему с HackerRank или подобного сайта.
Кроме того, Никита, тайм-аут — это не ошибка времени выполнения, это состояние сбоя на любом сайте испытаний, на котором вы находитесь, что указывает на то, что ваше решение решает проблему слишком медленно. Ваш код может компилироваться и работать и быть совершенно стабильным юридическим кодом, который правильно решает проблему, но он слишком медленный для вашей задачи. Я собираюсь догадаться, потому что на основе вложенности вашего цикла это выглядит как O (n ^ 3) или O (n ^ 4).
@Никита, поведение сильно зависит от ввода. Предоставьте (упрощенный) ввод, который приводит к тайм-ауту.
Хорошая практика: всегда проверяйте правильность ввода пользователя (также проверяйте состояние потока!). Вы обходите довольно много проблем, если пользователь вводит что-то недопустимое...
О используя пространство имен std...
Флаг, необходимый для выхода из вложенного цикла, довольно уродлив. Это был бы один из (довольно немногих) случаев, когда использование goto
было бы допустимым. Лямбда return
ing из вложенного цикла является альтернативой...
Вам вообще не нужен двойной цикл, если вы помните, что первая пара начинается с правильного чтения всех пар из пользовательского ввода.
Предположим, что пользователь установил 1 для обеих пар (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++).
вы, кажется, используете i и j для входов r и c и определяете r и c в начале. Зачем?