Hikaruchan
Grünschnabel
Hi erstmal!
Ich versuche gerade in einer kleinen testimplementierung diesen Algorithmus http://drdobbs.com/database/184410529?pgno=1 http://drdobbs.com/database/184410529?pgno=1 aus Listing Four zu implementieren. Prinzipiell versteh ich den Algorithmus, allerdings kommt es in meiner Implementierung immer zu einer Assertion mit der Expression: vector iterator + offset out of range.
Meiner Meinung dürfte der Fehler nicht auftreten, aber sowie es scheint, übersehe ich etwas. Nur für den Fall das es wichtig sein sollte, ich mache das ganz mit Visual Studio 2010, es handelt sich um eine C++ Console Application.
Nachfolgend poste ich mal meinen Code, ich glaub die Variablennamen sprechen für sich, falls nicht dann nachfragen *g*, beziehungsweise sind großteils gleich dem beschriebenen Algorithmus des obigen Links.
Ich hoffe es sieht jemand vl. den Fehler, ich sehs nicht, vermutlich is es eh was ganz blödes einfaches. *g*
Ich versuche gerade in einer kleinen testimplementierung diesen Algorithmus http://drdobbs.com/database/184410529?pgno=1 http://drdobbs.com/database/184410529?pgno=1 aus Listing Four zu implementieren. Prinzipiell versteh ich den Algorithmus, allerdings kommt es in meiner Implementierung immer zu einer Assertion mit der Expression: vector iterator + offset out of range.
Meiner Meinung dürfte der Fehler nicht auftreten, aber sowie es scheint, übersehe ich etwas. Nur für den Fall das es wichtig sein sollte, ich mache das ganz mit Visual Studio 2010, es handelt sich um eine C++ Console Application.
Nachfolgend poste ich mal meinen Code, ich glaub die Variablennamen sprechen für sich, falls nicht dann nachfragen *g*, beziehungsweise sind großteils gleich dem beschriebenen Algorithmus des obigen Links.
Ich hoffe es sieht jemand vl. den Fehler, ich sehs nicht, vermutlich is es eh was ganz blödes einfaches. *g*
Code:
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
int mapsize = 10;
void init(char** map){
srand(time(0));
for(int i = 0; i<mapsize; ++i){
cout<<"\n";
for(int j = 0; j<mapsize; ++j){
map[i][j] = (int)(rand()/(double)(RAND_MAX)+0.8)+'0';
}
}
for(int i = 0; i<mapsize; ++i){
cout<<"\n";
for(int j = 0; j<mapsize; ++j){
cout<<map[i][j];
}
}
cout<<"\n\n";
}
struct Pos{
int x;
int y;
Pos(){
x = 0;
y = 0;
}
Pos(int x, int y){
this->x = x;
this->y = y;
}
};
struct Rectangle{
Pos ur;
Pos ll;
Rectangle(){
ur = Pos(-1,-1);
ll = Pos(0,0);
}
Rectangle(Pos ur, Pos ll){
this->ur = ur;
this->ll = ll;
}
};
struct TempRect{
int startPos;
int width;
TempRect(int startPos, int width){
this->startPos = startPos;
this->width = width;
}
};
int area(Rectangle best_rect){
if (best_rect.ll.x > best_rect.ur.x || best_rect.ll.y > best_rect.ur.y){ // If ur is left of or
return 0; // below 11: return 0
}
else{
return (best_rect.ur.x-best_rect.ll.x+1)*(best_rect.ur.y-best_rect.ll.y+1);
}
}
void update_cache(int x, char** map, int* cache){
for(int y = 0; y < mapsize; y++){
if(map[x][y] != '0'){
cache[y] = cache[y]+1;
}else{
cache[y] = 0;
}
}
}
void findBiggestRectangle(char** map){
int* cache = new int[mapsize];
vector<TempRect> rectangle_stack;
Rectangle best_rect;
TempRect oldRect(0,0);
for(int i = 0; i < mapsize; i++){
cache[i] = 0;
}
int width = 0;
for(int x = mapsize-1; x >= 0; x--){
update_cache(x, map, cache);
width = 0;
for(int y = 0; y < mapsize; ++y){
if(cache[y] > width){
rectangle_stack.push_back(TempRect(y, width));
width = cache[y];
} else if(cache[y] < width){
do{
cout<<rectangle_stack.size();
oldRect = TempRect(rectangle_stack.back().startPos, rectangle_stack.back().width);
//oldRect = rectangle_stack.back();
rectangle_stack.pop_back();
if(width*(y-oldRect.startPos) > area(best_rect)){
best_rect.ll = Pos(x, oldRect.startPos);
best_rect.ur = Pos(x + width-1, y-1);
}
width = oldRect.width;
}while(cache[y] >= width && rectangle_stack.size() != 0);
width = cache[y];
if(width !=0){
rectangle_stack.push_back(TempRect(oldRect.startPos, width));
}
}
}
}
cout<<"ll x: "<<best_rect.ll.x<<" ll y: "<<best_rect.ll.y<<endl;
cout<<"ur x: "<<best_rect.ur.x<<" ur y: "<<best_rect.ur.y<<endl;
for(int j = best_rect.ll.y; j <= best_rect.ur.y; ++j){
for(int i = best_rect.ll.x; i <= best_rect.ur.x; ++i){
map[i][j] = 'x';
}
}
for(int i = 0; i<mapsize; ++i){
cout<<"\n";
for(int j = 0; j<mapsize; ++j){
cout<<map[i][j];
}
}
cout<<"\n\n";
}
int main(void){
char** map = new char*[mapsize];
for(int i = 0; i < mapsize; ++i) {
map[i] = new char[mapsize];
}
for(int i = 0; i<mapsize; ++i){
//cout<<"\n";
for(int j = 0; j<mapsize; ++j){
map[i][j] = '0';
//cout<<map[i][j];
}
}
//cout<<"\n\n";
init(map);
findBiggestRectangle(map);
return 0;
}
Zuletzt bearbeitet:
