Тема: Максимальное число вложенных параллелепипедов
Привет,
Условие задачи простое: найти максимальное количество вложенных параллелепипедов.
Параллелепипед может входить в другой только тогда, когда размеры его сторон строго меньше.
1?N?100
1?x,y,z?1000000
Пример входных данных:
4
1 1 1
2 2 2
3 4 5
4 3 2
Пример выходных данных:
3
У меня есть решение и оно не проходит все тесты.
Я не знаю где ошибка, на каком тесте заваливается по ВА.
Помогите пожалуйста, определить случай, когда этот код выдает ВА:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define X 0
#define Y 1
#define Z 2
struct CSuitCase
{
int m_size[3];
void Normalize()
{
sort(m_size, m_size+3);
}
bool operator < (const CSuitCase & suit2) const
{
bool bRetVal = false;
if(m_size[X] < suit2.m_size[X] &&
m_size[Y] < suit2.m_size[Y] &&
m_size[Z] < suit2.m_size[Z])
{
bRetVal = true;
}
return bRetVal;
}
};
bool matr[101][101];
int maxs[101];
void dfs(int v, vector<int> vect)
{
vect.push_back(v);
for(size_t i = 0; i < 101; ++i)
{
if(matr[i][v])
{
if(maxs[i] == 0)
{
dfs(i, vect);
}
}
}
for(size_t i = 0; i < vect.size(); ++i)
{
int m = vect.size() - i;
if(m > maxs[vect[i]] )
{
maxs[vect[i]] = m;
}
}
vect.pop_back();
}
int main()
{
vector<CSuitCase> suitcases;
memset(maxs, 0, sizeof(int)*101);
int nSuitCaseNumber;
cin >> nSuitCaseNumber;
for(size_t i = 0; i < nSuitCaseNumber; ++i)
{
CSuitCase suitCase;
scanf("%d %d %d", &suitCase.m_size[X], &suitCase.m_size[Y], &suitCase.m_size[Z]);
suitCase.Normalize();
suitcases.push_back(suitCase);
}
sort(suitcases.begin(), suitcases.end());
/*
for(size_t i = 0; i < suitcases.size(); ++i)
{
printf("%d %d %d\n", suitcases[i].m_size[X], suitcases[i].m_size[Y], suitcases[i].m_size[Z]);
}
*/
//
// Initialization
for(size_t i = 0; i < 101; ++i)
{
for(size_t j = 0; j < 101; ++j)
{
matr[i][j] = false;
}
}
//
// Creating of matr
for(size_t chosen = 0; chosen < suitcases.size(); ++chosen)
{
for(size_t i = chosen + 1; i < suitcases.size(); ++i)
{
if(suitcases[chosen] < suitcases[i])
{
matr[i][chosen] = true;
}
}
}
//
// Search for longest path
for(size_t i = 0; i < suitcases.size(); ++i)
{
vector<int> vect;
dfs(i, vect);
}
int nMax = 0;
for(size_t i = 0; i < 101; ++i)
{
if(maxs[i] > nMax)
{
nMax = maxs[i];
}
}
cout << nMax;
return 0;
}
Тому, кто найдет ответ, буду очень благодарен !