-2
以下は、グラフィックエディタのプログラミング課題の解決策です。詳細はhereです（解決には3日間かかりました）。出力が正しい間、time_limit_exceededエラーが生成され続けます。私は問題は、ユーザーが行の最初の文字として "F"を入力したときに呼び出されるflood_fill関数を実装した方法にあると思います。誰かが私のコードについて非常に非効率的で、どのように改善できるかを説明していただければ幸いです。私のコードは以下の通りです：グラフィックエディタのプログラミングの課題解決の時間制限を超えましたC++
// graphical_editor.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream> //provides access to cout and cin
#include <string> //Always import <string> if piping std input to a string in .net
#include <vector>
#include <fstream>
using std::ofstream;
using std::cin;
using std::cout;
using std::string;
using std::vector;
//This is where we store the pixels of the image
static vector<vector <string>> image_array;
ofstream myfile;
//our definition of an X,Y coordinate pair.
typedef struct point {
int x_coordinate, y_coordinate;
};
void initialise_image();
void clear_image();
void save_image(string file_name);
int get_image_width();
int get_image_height();
void color_pixel(int x, int y, string color);
void color_point(point p, string color);
void color_vertical_line(int x, int y1, int y2, string color);
void color_horizontal_line(int x1, int x2, int y, string color);
void color_box(int x1, int x2, int y1, int y2, string color);
void flood_fill(point p, string color);
vector<point> get_matching_neighbours(point p, string color);
int main()
{
string command; //first letter of a given line
myfile.open("example.txt");
while (cin >> command) {
//application terminates when command is X
if (command.compare("X") == 0) {
return 0;
} else if (command.compare("I") == 0) {
initialise_image();
}
else if (command.compare("S") == 0) {
string file_name;
cin >> file_name;
save_image(file_name);
}
else if (command.compare("L") == 0) {
string color;
point p;
cin >> p.x_coordinate >> p.y_coordinate >> color;
color_point(p, color);
}
else if (command.compare("V") == 0) {
string color;
int x, y1, y2;
cin >> x >> y1 >> y2 >> color;
color_vertical_line(x, y1, y2, color);
}
else if (command.compare("H") == 0) {
string color;
int x1, x2, y;
cin >> x1 >> x2 >> y >> color;
color_horizontal_line(x1, x2, y, color);
}
else if (command.compare("K") == 0) {
string color;
int x1, x2, y1, y2;
cin >> x1 >> x2 >> y1 >> y2 >> color;
color_box(x1, x2, y1, y2, color);
}
else if (command.compare("F") == 0) {
string color;
point p;
cin >> p.x_coordinate >> p.y_coordinate >> color;
flood_fill(p, color);
}
else if (command.compare("C") == 0) {
clear_image();
}
}
return 0;
}
void initialise_image()
{
/*read parameters height and width*/
int width, height;
cin >> width >> height;
/*first we create a vector of vectors (numRows+1)x(numColumns matrix+1). */
image_array.clear();
for (int i = 0; i < width+ 1; i++) {
image_array.push_back(vector<string>());
}
/*then we initialize each element of it one by one*/
for (int colNo = 0; colNo < width + 1; colNo++) {
for (int rowNo = 0; rowNo < height + 1; rowNo++) {
image_array[colNo].push_back("O");
}
}
}
void clear_image() {
/*we initialize each element of it one by one*/
for (int y = 1; y < get_image_height()+1 ; y++) {
for (int x = 1; x < get_image_width()+1; x++) {
image_array[x][y] = "O";
}
}
}
void save_image(string file_name) {
myfile << file_name << "\n";
//cout << file_name << "\n";
for (int y = 1; y < get_image_height()+1; y++) {
for (int x = 1; x < get_image_width()+1; x++) {
myfile << image_array[x][y];
//cout << image_array[x][y];
}
myfile << "\n";
//cout << "\n";
}
myfile.close();
}
int get_image_width() {
return image_array.size()-1;
}
int get_image_height() {
return image_array[0].size()-1;
}
void color_point(point p, string color) {
color_pixel(p.x_coordinate,p.y_coordinate, color);
}
void color_pixel(int x, int y, string color) {
image_array[x][y] = color;
}
void color_vertical_line(int x, int y1, int y2, string color) {
for (int y = y1; y <= y2; y++) {
color_pixel(x, y, color);
}
}
void color_horizontal_line(int x1, int x2, int y, string color) {
for (int x = x1; x <= x2; x++) {
color_pixel(x, y, color);
}
}
void color_box(int x1, int x2, int y1, int y2, string color) {
for (int x = x1; x <= x2; x++) {
for (int y = y1; y <= y2; y++) {
color_pixel(x, y, color);
}
}
}
string get_point_color(point p) {
return image_array[p.x_coordinate][p.y_coordinate];
}
void flood_fill(point p, string color) {
vector <point> points_queue;
points_queue.push_back(p);
string original_color = get_point_color(p);
point current_point;
while (points_queue.size() > 0) {
current_point = points_queue[0];
//if the point shares a color with the original point then color it in the new color.
if (get_point_color(current_point).compare(original_color) == 0) {
color_point(current_point, color);
}
// remove current point from the queue
points_queue.erase(points_queue.begin());
// add it's neighbours to the queue
vector<point> matching_neighbours = get_matching_neighbours(current_point, original_color);
for (int i = 0; i < matching_neighbours.size(); i++) {
points_queue.push_back(matching_neighbours[i]);
}
}
}
bool is_valid_point(point p) {
if (p.x_coordinate >= 1 && p.x_coordinate < get_image_width() + 1 && p.y_coordinate >= 1 && p.y_coordinate < get_image_height() + 1) {
return true;
}
else {
return false;
}
}
vector<point> get_matching_neighbours(point p, string color) {
vector<point> neighbours;
point left_neighbour, right_neighbour, upper_neighbour, lower_neighbour;
left_neighbour.x_coordinate = p.x_coordinate - 1;
left_neighbour.y_coordinate = p.y_coordinate;
if (is_valid_point(left_neighbour) && get_point_color(left_neighbour).compare(color) == 0) {
neighbours.push_back(left_neighbour);
}
right_neighbour.x_coordinate = p.x_coordinate + 1;
right_neighbour.y_coordinate = p.y_coordinate;
if (is_valid_point(right_neighbour) && get_point_color(right_neighbour).compare(color) == 0) {
neighbours.push_back(right_neighbour);
}
upper_neighbour.x_coordinate = p.x_coordinate;
upper_neighbour.y_coordinate = p.y_coordinate + 1;
if (is_valid_point(upper_neighbour) && get_point_color(upper_neighbour).compare(color) == 0) {
neighbours.push_back(upper_neighbour);
}
lower_neighbour.x_coordinate = p.x_coordinate;
lower_neighbour.y_coordinate = p.y_coordinate - 1;
if (is_valid_point(lower_neighbour) && get_point_color(lower_neighbour).compare(color) == 0) {
neighbours.push_back(lower_neighbour);
}
return neighbours;
}
ここでオンラインのコードジャッジエンジンに関する質問は控えてください。テストケースからどこに失敗したのかは誰にも分かりませんが、これは通常は公開されていないためです。テストしたものがあなたのローカル環境で実行されていたとしても、オンラインチャレンジに適用されるいくつかのエッジケースをテストすることができなかったかもしれません。創造的で見つけよう。さらに、オンラインコンテストを不正行為すること以外にも、長期的にそのような質問の価値はないと考えられ、何も学ばれていません。 –