# Lee Algorithm, traceback

Page 1 of 1

## 1 Replies - 15791 Views - Last Post: 17 December 2008 - 02:14 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=77211&amp;s=c03d08f9008db9898e954b4088581c6b&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Altemia

Reputation: 0
• Posts: 5
• Joined: 13-December 08

# Lee Algorithm, traceback

Posted 17 December 2008 - 11:48 AM

```//	Using a deque from the Standard Template Library as a FIFO queue.
//	Illustrating front() and back() methods

#include <iostream>
#include <list>
#include <deque>
#include <algorithm>
using namespace std;

list<int> listx;
list<int> listy;
list<int> listvals;
//
int board[10][10];
int input;
int a;
int b;
int i=0;
int j=0;
int value;
int startval;
int startval_;
int value2;
int value3;
int value4;
int value5;
int x;
int y;
int cv = 1;
bool found = false;
bool startfound =false;
bool check(int x, int y);
void display();
//
void main(){// main begin

deque<int> ideque;
//int column_pin1;
//int row_pin1;
//int column_pin2;
//int row_pin2;
//int column_pin1_top;
//int column_pin1_bottom;
//
while(1)
{//while loop begin
cout << endl;
cout << "1. display" <<endl;
cout << "3. search" <<endl;
cout << "4. traceback" <<endl;
cout << "5. exit" << endl;
cout << "cv";
cout<< cv;cout <<endl;
cin >> input;
if (input == 1)///////////////////////////////////////////
{//input 1 begin, display
display();
}//input 1 finish, display
else if (input == 2)//////////////////////////////////////////
cout << endl;
cout << "please give start position in row and start position in coloumn to found path from";
cin >> value2;//starting x
cin >> value3;//starting y
cout << "please give finish position in row and finish posiiton in coloumn to found path to";
cin >> value4;
cin >> value5;
value3 = value3-1, value2 = value2-1, value5 = value5-1, value4 = value4-1;//array starts at 0 so take one from these
//add these new positions to the board
board[value4][value5] = 1;
board[value2][value3] = 1;
else if (input ==3)/////////////////////////////////////////////
{//input 3 begin, search
int cx = value2;
int cy = value3;
int gx = value4;
int gy = value5;
board[value2][value3] = cv;
listx.push_front(value2);
listy.push_front(value3);
listvals.push_front(cv);
do{
cv = listvals.back();
cx = listx.back();
cy = listy.back();
///TOP////
x = cx;
y = cy + 1;
if((x > -1)&&(x < 10)&&(y > -1)&&(y < 10))
{
if(check(x,y) == false)
{
board[x][y] = (cv + 1);
listx.push_front(x);
listy.push_front(y);
listvals.push_front((cv + 1));
}
}
else
{
x = 0;
y = 0;
}
if((x == gx)&&(y == gy)){found = true;}
/////RIGHT/////
x = cx + 1;
y = cy;
if((x > -1)&&(x < 10)&&(y > -1)&&(y < 10))
{
if(check(x,y) == false)
{
board[x][y] = (cv + 1);
listx.push_front(x);
listy.push_front(y);
listvals.push_front((cv + 1));
}
}
else
{
x = 0;
y = 0;
}
if((x == gx)&&(y == gy)){found = true;}
/////BOTTOM/////
x = cx;
y = cy - 1;
if((x > -1)&&(x < 10)&&(y > -1)&&(y < 10))
{
if(check(x,y) == false)
{
board[x][y] = (cv + 1);
listx.push_front(x);
listy.push_front(y);
listvals.push_front((cv + 1));
}
}
else
{
x = 0;
y = 0;
}
if((x == gx)&&(y == gy)){found = true;}
/////LEFT/////
x = cx - 1;
y = cy;
if((x > -1)&&(x < 10)&&(y > -1)&&(y < 10))
{
if(check(x,y) == false)
{
board[x][y] = (cv + 1);
listx.push_front(x);
listy.push_front(y);
listvals.push_front((cv + 1));
}
}
else
{
x = 0;
y = 0;
}
if((x == gx)&&(y == gy)){found = true;}
/////////////DIAGONAL RIGHT TOP/////////
x = cx + 1;
y = cy + 1;
if((x > -1)&&(x < 10)&&(y > -1)&&(y < 10))
{
if(check(x,y) == false)
{
board[x][y] = (cv + 1);
listx.push_front(x);
listy.push_front(y);
listvals.push_front((cv + 1));
}
}
else
{
x = 0;
y = 0;
}
//listx.pop_back();
//listy.pop_back();
//listvals.pop_back();
if((x == gx)&&(y == gy)){found = true;}
/////////////DIAGONAL RIGHT BOTTOM/////////
if((x == gx)&&(y == gy)){found = true;}
x = cx + 1;
y = cy -1;
if((x > -1)&&(x < 10)&&(y > -1)&&(y < 10))
{
if(check(x,y) == false)
{
board[x][y] = (cv + 1);
listx.push_front(x);
listy.push_front(y);
listvals.push_front((cv + 1));
}
}
else
{
x = 0;
y = 0;
}
//listx.pop_back();
//listy.pop_back();
//listvals.pop_back();
if((x == gx)&&(y == gy)){found = true;}
/////////////DIAGONAL LEFT BOTTOM/////////
if((x == gx)&&(y == gy)){found = true;}
x = cx - 1;
y = cy - 1;
if((x > -1)&&(x < 10)&&(y > -1)&&(y < 10))
{
if(check(x,y) == false)
{
board[x][y] = (cv + 1);
listx.push_front(x);
listy.push_front(y);
listvals.push_front((cv + 1));
}
}
else
{
x = 0;
y = 0;
}
//listx.pop_back();
//listy.pop_back();
//listvals.pop_back();
if((x == gx)&&(y == gy)){found = true;}
/////////////DIAGONAL LEFT TOP/////////
if((x == gx)&&(y == gy)){found = true;}
x = cx - 1;
y = cy + 1;
if((x > -1)&&(x < 10)&&(y > -1)&&(y < 10))
{
if(check(x,y) == false)
{
board[x][y] = (cv + 1);
listx.push_front(x);
listy.push_front(y);
listvals.push_front((cv + 1));
}
}
else
{
x = 0;
y = 0;
}
if((x == gx)&&(y == gy)){found = true;}
board[gx+1][gy+1]=1;
board[gx][gy]=cv+1;
cv = cv+1;
listx.pop_back();
listy.pop_back();
listvals.pop_back();
/////
}while (found ==false /*|| all points marked*/);
}//input 3 finish, search
else if (input ==4)
{// input 4 begin, traceback
int gx = value4;//[y][x]
int gy = value5;//[y][x]
y = gx;
x = gy;
int val;
//startfound=true;
//int cv=board[x][y];
//val = board[x][y] /*board[gx][gy]*/;
//board[x][y]=cv;
val = board[gx][gy];
board[gx][gy] = -1;
do{
//top
gy++;
if(((x+1) > -1)&&((x+1) < 10)&&((y+1) > -1)&&((y+1) < 10)&&(board[x][y + 1] > 0)&&(board[x][y + 1] < val))
{
val = board[gx][gy];//board[x][y]
board[gx][gy] = -1;//[y][x]
}
else{
//top right
gx++;
gy++;
if(((x+1) > -1)&&((x+1) < 10)&&((y+1) > -1)&&((y+1) < 10)&&(board[x + 1][y + 1] > 0)&&(board[x + 1][y + 1] < val))
{
val = board[gx][gy];//board[x][y];
board[gx][gy] = -1;//[y][x]
}else{
// right
gx++;
if(((x+1) > -1)&&((x+1) < 10)&&((y-1) > -1)&&((y-1) < 10)&&(board[x + 1][y] > 0)&&(board[x + 1][y] < val))
{
val = cv-1;//board[x][y];
board[gx][gy] = -1;//[y][x]
}else{
//bottomright
gx++;
gy--;
if((x > -1)&&(x < 10)&&((y-1) > -1)&&((y-1) < 10)&&(board[x + 1][y - 1] > 0)&&(board[x + 1][y - 1] < val))
{
val = cv-1;//board[x][y];
board[gx][gy] = -1;
}else{
//bottom
gy--;
if(((x-1) > -1)&&((x-1) < 10)&&((y+1) > -1)&&((y+1) < 10)&&(board[x][y - 1] > 0)&&(board[x][y - 1] < val))
{
val = cv-1;//board[x][y];
board[gx][gy] = -1;
}else{
//bottom left
gy--;
gx--;
if((x > -1)&&(x < 10)&&(y > -1)&&(y < 10)&&(board[x - 1][y - 1] > 0)&&(board[x - 1][y - 1] < val))
{
val = cv-1;//board[x][y];
board[gx][gy] = -1;
}else{
//left
gx--;
if(((x-1) > -1)&&((x-1) < 10)&&(y > -1)&&(y < 10)&&(board[x - 1][y] > 0)&&(board[x - 1][y] < val))
{
val = cv-1;//board[x][y];
board[gx][gy] = -1;
}else{
// top left
gy++;
gx--;
if(((x-1) > -1)&&((x-1) < 10)&&((y+1) > -1)&&((y+1) < 10)&&(board[x - 1][y + 1] > 0)&&(board[x - 1][y + 1] < val))
{
val = cv-1;//board[x][y];
board[gx][gy] = -1;
}else{}}}}}}}}
if((gx == value3)&&(gy == value2)){startfound = true;}
}while(startfound==false);
}// input 4 end, traceback
else if (input ==5)////
{//input 5 begin, exit
exit(1);
}// input 5 finish, exit
}//while loop end
}//main end

void display()
{//display function
cout << endl;
for (a=0; a<10; a++)
{
for (b=0; b<10; b++)
{
cout << board[a][b];
cout << "	";
//cout <<endl;
}
}
cout << endl; cout<<endl;
}//display fucntion

bool check(int x, int y)
{
if(board[x][y] == 0)
{
return false;
}
else
{
return true;
}
}

```

I understand that my code is a mess and that it's all in the one function but until I figure out how to get traceback working I shan't bother putting it in fucntions since i'm snowed under with other coursework at the moment.

This code takes in two values and branches out from the first until it finds the second. Once it finds the Second value it should traceback to the first by the shortest route. I'm stressed because I can't work out why it won't do this and the mess of code makes it worse.

The output should be along the lines of:

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 2 3 4 0 0 0 0
0 0 2 -1 3 4 0 0 0 0
0 0 3 3 -1 -1 1 0 0 0
0 0 4 4 4 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

the -1s being the route and the 1s being the inputs.

Can anyone explain to me why it dosn't work?

Is This A Good Question/Topic? 0

## Replies To: Lee Algorithm, traceback

### #2 janotte

• code > sword

Reputation: 991
• Posts: 5,141
• Joined: 28-September 06

## Re: Lee Algorithm, traceback

Posted 17 December 2008 - 02:14 PM

You are coming at this from the wrong end.

The whole point of using functions is that they allow a 'divide and conquer' approach to your solution. Breaking your solution down into pieces and writing a function to do each chunk is the key to developing anything more than the simplest of programs.

Once you have a function that you are sure does 'X' just as you expect/want then you can put that chunk out of your mind and move to the next challenge.

Building a monolith that requires holding the whole logic in your head is a bad idea. Worse to then attempt to strip it back down and build functions as the last step.

You have described what you want the output to be but you have not supplied any details of "why it dosn't work". Do you have compile errors / warnings? Do you have examples of faulty outcomes / outputs to share?

Lastly if you know your code is a mess and difficult to read and understand you are asking a lot of the kindness of strangers to expect them to slog through all your logic puzzles to try and help you. If you don't have time to work on it then asking others to do so is asking a lot.

I very much hope someone has the time and patience to do just that for you but I don't have that much time or energy so I'll just wish you good luck and answer to the other calls on my time.