Lee algorithm help needed

[Rob111]

Hello,
I need help with Lee algorithm. Just a quick reminder of what it is: Start at a point, assign the cost of 0 to that point, and expand vertically and horizontally until target is hit. See below:
______3
____3 2 3
__3 2 1 2 3
3 2 1 0 1 2 3
__3 2 1 2 3
___3 2 3
_____3

Let's assume pin 1 (row_pin1 and column_pin1) and pin 2 (row_pin2 and column_pin2) definitions are correct. Also, please ignore all printf statements, I use them just to see where my program is going.

Where I am lost is at the logic of the expansion from point 0 to the target. Can someone please help me with that?

Also, if you look at Lee algorithm, I think with the current values, "while" loop should never be exited, because even though row_pin1=row_pin2, column_pin1!=column_pint. But the loop exits anyway, rather than getting stuck.

/* --- The following code comes from C:\lcc\lib\wizard\textmode.tpl. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
main()
{
int x=5;
int array[6];
array[0]=0; 
array[1]=2;
array[2]=1;
array[3]=3;
array[4]=4;
array[5]=1;
int column_pin1;
int row_pin1;
int column_pin2;
int row_pin2;
int column_pin1_top;
int column_pin1_bottom;
int cost=0;
//-Pin 1
if (array[2]==0 && (array[1]!=0 && array[1]!=x-1))
{
column_pin1=array[0];
row_pin1=array[1]+1;
printf("%3i", column_pin1);
}
if (array[2]==0 && (array[1]==0 || array[1]==x-1))
{
column_pin1=array[0];
row_pin1=array[1]+1;
printf("%3i", column_pin1);
}
if (array[2]==1)
{
column_pin1=array[0];
row_pin1=array[1];
printf("%3i", column_pin1);
}
if (array[2]==2)
{
column_pin1=array[0];
row_pin1=array[1];
printf("%3i", column_pin1);
}
if (array[2]==3)
{
column_pin1=array[0]+1;
row_pin1=array[1];
printf("%3i", column_pin1);
}
if (array[2]==4)
{
column_pin1=array[0]+1;
row_pin1=array[1];
printf("%3i", column_pin1);
}
//-Pin 2
if (array[5]==0 && (array[4]!=0 && array[4]!=x-1))
{
column_pin2=array[3];
row_pin2=array[4]+1;
printf("%3i", column_pin2);
}
if (array[5]==0 && (array[4]==0 || array[4]==x-1))
{
column_pin2=array[3];
row_pin2=array[4]+1;
printf("%3i", column_pin2);
}
if (array[5]==1)
{
column_pin2=array[3];
row_pin2=array[4];
printf("%3i", column_pin2);
}
if (array[5]==2)
{
column_pin2=array[3];
row_pin2=array[4];
printf("%3i", column_pin2);
}
if (array[5]==3)
{
column_pin2=array[3]+1;
row_pin2=array[4];
printf("%3i", column_pin2);
}
if (array[5]==4)
{
column_pin2=array[3]+1;
row_pin2=array[4];
printf("%3i", column_pin2);
}
//- Lee algorithm
while (((row_pin1)!=(row_pin2)) && ((column_pin1)!=(column_pin2)))
{
column_pin1_top=column_pin1;
printf("%3i", column_pin1_top);
column_pin1_bottom=column_pin1;
printf("kk");
printf("%3i", cost);
//- going to the right
for (row_pin1=row_pin1;row_pin1!=row_pin2;row_pin1++)
{
printf("%3i", cost);
column_pin1_top=column_pin1_top+1;
printf("%3i", column_pin1_top);
column_pin1_bottom=column_pin1_bottom-1;
cost=cost+1;
if (column_pin1_top==column_pin2)
{
column_pin1=column_pin1_top;
}
if (column_pin1_bottom==column_pin2)
{
column_pin1=column_pin1_bottom;
}
printf("%3i", cost);
printf("%3i", column_pin1_top);
printf("%3i", column_pin1_bottom);
printf("%3i", column_pin1);
}
}
}

Thank You.

[Salem]

> The following code comes from C:\lcc\lib\wizard\textmode.tpl
Nevermind that, where is YOUR code?
You write code, get stuck, post your code and ask direct questions about your code.
We then help you to figure out the solution to your immediate problem.

We're not here to explain code you just "found" which may (or may not) actually solve the problem.

Plus the fact that the code you posted has no indentation at all, which is a big turn-off to even bothering to look at it.

[Rob111]

> The following code comes from C:\lcc\lib\wizard\textmode.tpl
Nevermind that, where is YOUR code?
You write code, get stuck, post your code and ask direct questions about your code.
We then help you to figure out the solution to your immediate problem.

We're not here to explain code you just "found" which may (or may not) actually solve the problem.

Plus the fact that the code you posted has no indentation at all, which is a big turn-off to even bothering to look at it.

This is MY code, with lcc compiler you need to create and then open(if you closed it and worked with the other project) the project first, else it would compile the file to the previous project's directory (took me half an hour to figure out that one) and you can use the wizard for that. So much for the accusations. That's why I said "assume pin 1 (row_pin1 and column_pin1) and pin 2 (row_pin2 and column_pin2) definitions are correct".

[Lerner]

I have no idea what the Lee algorhithm is, or isn't. However, given your description and your post, I presume you could do something like this.

The pattern presented can be considered as a series of lines on top and a series of lines on bottom where

Each line has spaces followed by ints and

The ints initially decline from target and then increment back to target and

The number of decrements is always the same as the number of increments in each line.

If you let
target number be input by user
then
n = line number, start at 0 on top and 1 on bottom
t = control the ints
x = number of spaces before ints = target - n
y = number of decrements (which is the same as the number of increments) done per line = target - n

and you could probably flesh out the following schema to produce the pattern:

Top
//loop to control lines
  //loop to print spaces
  //loop to print decreasing ints
  //loop to print increasing ints

Bottom
//loop to control lines
  //loop to print spaces
  //loop to print decreasing ints
  //loop to print increasing ints

[Rob111]

I have no idea what the Lee algorhithm is, or isn't. However, given your description and your post, I presume you could do something like this.

The pattern presented can be considered as a series of lines on top and a series of lines on bottom where

Each line has spaces followed by ints and

The ints initially decline from target and then increment back to target and

The number of decrements is always the same as the number of increments in each line.

If you let
target number be input by user
then
n = line number, start at 0 on top and 1 on bottom
t = control the ints
x = number of spaces before ints = target - n
y = number of decrements (which is the same as the number of increments) done per line = target - n

and you could probably flesh out the following schema to produce the pattern:

Top
//loop to control lines
  //loop to print spaces
  //loop to print decreasing ints
  //loop to print increasing ints
 
Bottom
//loop to control lines
  //loop to print spaces
  //loop to print decreasing ints
  //loop to print increasing ints

Here is what I have thus far:
What I want/can do is have GridPoint expand from the source to the target, but I am having hard time creating the loop. There is no need for spaces, I added them for visibility. I can do what you suggested (if I understood it correctly, I could be wrong), such as go north/south first, and then east west, but that wouldn't really be Lee algorithm. What Lee algorithm should is is the following go west from the source (point 1), go east the source (point 2), go south from the source, go north from the source. Then, go west from point 1, go south from point 1, go north from point 1 (can't go east from point 1 because that's going backwards), etc. This will be important once I add obstacles (e.g., point 2 is blocked, and the target is 3 points east from the source, so you need to go around obstacle).

/* --- The following code comes from C:\lcc\lib\wizard\textmode.tpl. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct GridPoint{int x; int y;};
void initExpand() {int val = 0; };
//void GridPoint northNeighbor {int x=x;int y=y-1};

int main()
{
 int x = 0;
 int y = 0;
 // open the file for reading
 FILE* fp = fopen("fcct1","r");
 if (fp==NULL) {fputs ("File error",stderr); exit (1);}
 // read x and y
 fscanf(fp,"%d", &x);
 fscanf(fp,"%d", &y);
   // allocate first row
   int **array = malloc( sizeof(int*) );
   // allocate 6 columns
   array[0] = malloc( 6 * sizeof(int));
   int numRows = 0;
   unsigned int n=0;
   int row = 0;
   int col = 0;
   while( fscanf(fp,"%d", &n) > 0)
   {
   if( col < 6)
      {
      array[row][col] = n;
         ++col;
    }
   else
    {
         ++row;
         array = realloc(array,row * sizeof(int*));
         array[row] = malloc( 6 * sizeof(int));
   col = 0;
         array[row][col] = n;
         ++col;
   }
    }
   printf("%i", array[0][1]);

 printf("%i", row);
int column_pin1;
int row_pin1;
int column_pin2;
int row_pin2;
int column_pin1_top;
int column_pin1_bottom;
int cost=0;
int row_max=row;
for (row=0;row<row_max-1;row++)
{
//-Pin 1
if (array[row][2]==0 && (array[row][1]!=0 && array[row][1]!=x-1))
 {
 column_pin1=array[row][0];
 row_pin1=array[row][1]+1;
    printf("%3i", column_pin1);
}
if (array[row][2]==0 && (array[row][1]==0 || array[row][1]==x-1))
 {
 column_pin1=array[row][0];
 row_pin1=array[row][1]+1.;
    printf("%3i", column_pin1);
}
if (array[row][2]==1)
 {
 column_pin1=array[row][0];
 row_pin1=array[row][1];
 printf("%3i", column_pin1);
}
if (array[row][2]==2)
 {
 column_pin1=array[row][0];
 row_pin1=array[row][1];
 printf("%3i", column_pin1);
}
if (array[row][2]==3)
 {
 column_pin1=array[row][0]+1;
 row_pin1=array[row][1];
 printf("%3i", column_pin1);
}
if (array[row][2]==4)
 {
 column_pin1=array[row][0]+1;
 row_pin1=array[row][1];
 printf("%3i", column_pin1);
}
//-Pin 2
if (array[row][5]==0 && (array[row][4]!=0 && array[row][4]!=x-1))
 {
 column_pin2=array[row][3];
 row_pin2=array[row][4]+1;
    printf("%3i", column_pin2);
}
if (array[row][5]==0 && (array[row][4]==0 || array[row][4]==x-1))
 {
 column_pin2=array[row][3];
 row_pin2=array[row][4]+1;
    printf("%3i", column_pin2);
}
if (array[row][5]==1)
 {
 column_pin2=array[row][3];
 row_pin2=array[row][4];
 printf("%3i", column_pin2);
}
if (array[row][5]==2)
 {
 column_pin2=array[row][3];
 row_pin2=array[row][4];
 printf("%3i", column_pin2);
}
if (array[row][5]==3)
 {
 column_pin2=array[row][3]+1;
 row_pin2=array[row][4];
 printf("%3i", column_pin2);
}
if (array[row][5]==4)
 {
 column_pin2=array[row][3]+1;
 row_pin2=array[row][4];
 printf("%3i", column_pin2);
}
struct GridPoint z;
 z.x=row;
 z.y=col;
struct GridPoint southNeighbor;
    southNeighbor.x=x;
 southNeighbor.y=y+1;
struct GridPoint northNeighbor;
    northNeighbor.x=x;
 northNeighbor.y=y-1;
struct GridPoint westNeighbor;
    westNeighbor.x=x-1;
 westNeighbor.y=y;
struct GridPoint eastNeighbor;
    eastNeighbor.x=x;
 eastNeighbor.y=y+1;
}
}

[Rob111]

It is similar to this:

http://foghorn.cadlab.lafayette.edu/cadapplets/MazeRouter.html

except that code is in Java, of course.

[Rob111]

So, my problem is: how do I go east, then west, then south, then north and increment the cost (or the step, whatever you want to call it) only by 1 and then start from the from the first step west and repeat the same procedure (I think I know how to not go back, so that's ok).

[Rob111]

I also must remember the cost (in order to do tracebaack from target to source).

[Rob111]

I guess edit message dissapears after someone views the message. Anyway, *I think* I need to create an array in which to store the values of coordniates and cost for that particular coordinate.
So, here is the structure,
struct GridPoint{int x; int y; int val;};

and I would like to perform moves such as
z=westNeighbor;
z.val=val+1;

on the each element (of course without going to the elements which I already visited) AND enqueue the obtained elements (with their cost for subsequent processes).

Can someone help me out with this, please? (and how to go between elements in the array)

And while I have your attention,

why does my for loop crashes during running:
for (row=0;row<row_max;row++),

but runs fine for
for (row=0;row<row_max-1;row++)

This causes me to loose one row of data (it is not the row of -1s, it is actually useful data I am missing).

[Rob111]

One more thing:
I need to memorize which path is used for subsequent iterations (e.g., if I'm using path 2,2->2,1->2,0 and 3,1->2,1->2,2, I can not use 2,1-2,2 nomore if only two connections through that path are allowed).

[Rob111]

The code I previously posted looks hard to read, so I am reposting (with slight changes).

/* --- The following code comes from C:\lcc\lib\wizard\textmode.tpl. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct GridPoint{int x; int y; int val;};
//void initExpand() {int val = 0; };
//void GridPoint northNeighbor {int x=x;int y=y-1};

int main()
{
 int x = 0; // number of rows and columns
 int y = 0; // number of routing tracks per channel
 // open the file for reading
 FILE* fp = fopen("fcct1","r");
 if (fp==NULL) {fputs ("File error",stderr); exit (1);}
 // read x and y
 fscanf(fp,"%d", &x);
 fscanf(fp,"%d", &y);
   // allocate first row
   int **array = malloc( sizeof(int*) );
   // allocate 6 columns
   array[0] = malloc( 6 * sizeof(int));
   int numRows = 0;
   unsigned int n=0;
   int row = 0;
   int col = 0;
   while( fscanf(fp,"%d", &n) > 0)
   {
   if( col < 6)
      {
      array[row][col] = n;
         ++col;
    }
   else
    {
         ++row;
         array = realloc(array,row * sizeof(int*));
         array[row] = malloc( 6 * sizeof(int));
   col = 0;
         array[row][col] = n;
         ++col;
   }
    }
   printf("%i", array[0][1]);

 printf("%i", row);
int column_pin1;
int row_pin1;
int column_pin2;
int row_pin2;
int column_pin1_top;
int column_pin1_bottom;
int cost=0;
int row_max=row;
for (row=0;row<row_max-1;row++)
{
//-Pin 1
if (array[row][2]==0 && (array[row][1]!=0 && array[row][1]!=x-1))
 {
 column_pin1=array[row][0];
 row_pin1=array[row][1]+1;
    printf("%3i", column_pin1);
}
if (array[row][2]==0 && (array[row][1]==0 || array[row][1]==x-1))
 {
 column_pin1=array[row][0];
 row_pin1=array[row][1]+1.;
    printf("%3i", column_pin1);
}
if (array[row][2]==1)
 {
 column_pin1=array[row][0];
 row_pin1=array[row][1];
 printf("%3i", column_pin1);
}
if (array[row][2]==2)
 {
 column_pin1=array[row][0];
 row_pin1=array[row][1];
 printf("%3i", column_pin1);
}
if (array[row][2]==3)
 {
 column_pin1=array[row][0]+1;
 row_pin1=array[row][1];
 printf("%3i", column_pin1);
}
if (array[row][2]==4)
 {
 column_pin1=array[row][0]+1;
 row_pin1=array[row][1];
 printf("%3i", column_pin1);
}
//-Pin 2
if (array[row][5]==0 && (array[row][4]!=0 && array[row][4]!=x-1))
 {
 column_pin2=array[row][3];
 row_pin2=array[row][4]+1;
    printf("%3i", column_pin2);
}
if (array[row][5]==0 && (array[row][4]==0 || array[row][4]==x-1))
 {
 column_pin2=array[row][3];
 row_pin2=array[row][4]+1;
    printf("%3i", column_pin2);
}
if (array[row][5]==1)
 {
 column_pin2=array[row][3];
 row_pin2=array[row][4];
 printf("%3i", column_pin2);
}
if (array[row][5]==2)
 {
 column_pin2=array[row][3];
 row_pin2=array[row][4];
 printf("%3i", column_pin2);
}
if (array[row][5]==3)
 {
 column_pin2=array[row][3]+1;
 row_pin2=array[row][4];
 printf("%3i", column_pin2);
}
if (array[row][5]==4)
 {
 column_pin2=array[row][3]+1;
 row_pin2=array[row][4];
 printf("%3i", column_pin2);
}
struct GridPoint z;
 z.x=row_pin1;
 z.y=column_pin1;
struct GridPoint southNeighbor;
    southNeighbor.x=x;
 southNeighbor.y=y+1;
struct GridPoint northNeighbor;
    northNeighbor.x=x;
 northNeighbor.y=y-1;
struct GridPoint westNeighbor;
    westNeighbor.x=x-1;
 westNeighbor.y=y;
struct GridPoint eastNeighbor;
    eastNeighbor.x=x+1;
 eastNeighbor.y=y;
int val=0;
 z=eastNeighbor;
 z.val=val+1;
 printf("%i", z.x);
//int val=0;
 z=westNeighbor;
 z.val=val+1;
 printf("%i", z.x);
 z=westNeighbor;
 z.val=val+1;
 printf("%i", z.x);
}
}