Witam,
Mocuję się z jednym zadaniem na Codewars. Program ma podawać piksele ze środka obszaru o zadanym kolorze.
Kod poniżej działa jak trzeba, ale nie przechodzi "Big Tests" czyli 16 Mpx obrazka (przekracza dozwolone 12s czasu wykonywania).
W jaki sposób mogę go zoptymalizować ? Czy muszę wyrzucić tworzenie matrycy i sprawdzać piksele wskaźnikiem ?
Link do zadania: https://www.codewars.com/kata/centre-of-attention
#include <algorithm>
#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
struct myImage
{
vector<vector<unsigned>> matrix;
vector<unsigned> shortest_route, ret_vector;
unsigned width, height, *pixels, color, max_depth = 0;
myImage(const unsigned &w, const unsigned &h, unsigned *p, const unsigned &c) : width(w), height(h), pixels(p), color(c)
{ }
void conjure_up_matrix();
vector<unsigned> central_pixels(unsigned colour);
void assert_depth();
unsigned find_depth(const int &row, const int &col);
inline bool is_outof_bounds(const int &row, const int &col, const int &steps);
inline void get_depth_linear_directions(const int &row, const int &col);
inline int get_depth_sides(const int &row, const int &col, const int &max_steps);
};
void myImage::conjure_up_matrix()
{
unsigned col = 0;
unsigned row = 0;
this->matrix.resize(this->height, vector<unsigned>(this->width, 0));
for(unsigned i = 0; i < this->width*this->height; i++)
{
if(col >= this->width)
{
row++;
col = 0;
}
this->matrix[row][col++] = pixels[i];
}
}
vector<unsigned> Image::central_pixels(unsigned colour) const /// funkcja z innej struktury (zdef. przez autora zadania)
{
myImage myImg(this->width, this->height, this->pixels, colour);
myImg.conjure_up_matrix();
myImg.assert_depth();
return myImg.ret_vector;
}
void myImage::assert_depth()
{
this->shortest_route.reserve(200);
unsigned p_pos, p_depth, row=0, col=0;
for(unsigned *i = this->pixels, j=1; i<&this->pixels[this->width*this->height]; i++, j++)
{
if(*i == this->color)
{
p_pos = j-1;
p_depth = this->find_depth(row, col);
if(this->max_depth == p_depth)
this->ret_vector.emplace_back(p_pos);
else if(this->max_depth < p_depth)
{
this->max_depth = p_depth;
this->ret_vector.clear();
this->ret_vector.emplace_back(p_pos);
}
}
if(j%this->width == 0)
{
row++;
col=-1;
}
col++;
}
}
inline void myImage::get_depth_linear_directions(const int &row, const int &col)
{
int steps = 1;
while(!is_outof_bounds(row, col, steps) && this->matrix[row-steps][col] == this->color &&
this->matrix[row][col+steps] == this->color && this->matrix[row+steps][col] == this->color && this->matrix[row][col-steps] == this->color)
steps++;
if(this->get_depth_sides(row, col, steps) > 0)
this->shortest_route.emplace_back(this->get_depth_sides(row, col, steps));
this->shortest_route.emplace_back(steps);
}
inline int myImage::get_depth_sides(const int &row, const int &col, const int &max_steps)
{
for(int i=1; i<max_steps-1; i++)
{
for(int j=1; j<max_steps-1; j++)
{
if(this->matrix[row-i][col+j] != this->color ||
this->matrix[row-i][col-j] != this->color ||
this->matrix[row+i][col+j] != this->color ||
this->matrix[row+i][col-j] != this->color ||
this->matrix[row-j][col+i] != this->color ||
this->matrix[row+j][col+i] != this->color ||
this->matrix[row-j][col-i] != this->color ||
this->matrix[row+j][col-i] != this->color)
return i+j;
}
}
return 0;
}
unsigned myImage::find_depth(const int &row, const int &col)
{
this->shortest_route.clear();
get_depth_linear_directions(row, col);
sort(this->shortest_route.begin(), this->shortest_route.end());
if(this->shortest_route.size() > 0)
return this->shortest_route.front();
else
return 0;
}
inline bool myImage::is_outof_bounds(const int &row, const int &col, const int &steps)
{
if(row-steps < 0 || col-steps < 0 || row+steps >= this->height || col+steps >= this->width)
return true;
else
return false;
}
PS: kolorowanie składni wstawiłem jako c#. W jaki sposób zaznaczyć kod jako "c++" ?