Left-Right Pathfinding

[awilson161]

Hi. I wonder if anyone can help me. I am using C++ and i have created an array of the size X*Y (array[x][y]) where I later specify X and Y. The array is just 1s and 0s and I want to know if I can get to one side of the array to the other moving vertically, hoizontally and/or diagonally with just 1s, ie if there is a path of 1s through the array. Any suggestions???
Thanx

[weaknessforcats]

Nope. The array look like this in memory:

10101010101010101010101101010101010101....

You have to figure out bthe x and y value that makes it appear to be:

1010101010
1010101010
1011010101
01010101.....

There are no multi-dimensional array in C ot C++.

Read this:

First, there are only one-dimensional arrays in C or C++. The number of elements in put between brackets:

int array[5];
 

That is an array of 5 elements each of which is an int.

int array[];
 

won't compile. You need to declare the number of elements.

Second, this array:

int array[5][10];
 

is still an array of 5 elements. Each element is an array of 10 int.

int array[5][10][15];
 

is still an array of 5 elements. Each element is an array of 10 elements where each element is an array of 15 int.

int array[][10];
 

won't compile. You need to declare the number of elements.

Third, the name of an array is the address of element 0

int array[5];
 

Here array is the address of array[0]. Since array[0] is an int, array is the address of an int. You can assign the name array to an int*.

int array[5][10];
 

Here array is the address of array[0]. Since array[0] is an array of 10 int, array is the address of an array of 10 int. You can assign the name array to a pointer to an array of 10 int:

int array[5][10];
 
int (*ptr)[10] = array;
 

Fourth, when the number of elements is not known at compile time, you create the array dynamically:

int* array = new int[value];
int (*ptr)[10] = new int[value][10];
int (*ptr)[10][15] = new int[value][10][15];
 

In each case value is the number of elements. Any other brackets only describe the elements.

Using an int** for an array of arrays is incorrect and produces wrong answers using pointer arithmetic. The compiler knows this so it won't compile this code:

int** ptr = new int[value][10];    //ERROR
 

new returns the address of an array of 10 int and that isn't the same as an int**.

Likewise:

int*** ptr = new int[value][10][15];    //ERROR
 

new returns the address of an array of 10 elements where each element is an array of 15 int and that isn't the same as an int***.

With the above in mind this array:

int array[10] = {0,1,2,3,4,5,6,7,8,9};
 

has a memory layout of

0 1 2 3 4 5 6 7 8 9

Wheras this array:

int array[5][2] = {0,1,2,3,4,5,6,7,8,9};
 

has a memory layout of

0 1 2 3 4 5 6 7 8 9

Kinda the same, right?

So if your disc file contains

0 1 2 3 4 5 6 7 8 9

Does it make a difference wheher you read into a one-dimensional array or a two-dimensional array? No.

Therefore, when you do your read use the address of array[0][0] and read as though you have a
one-dimensional array and the values will be in the correct locations.

[awilson161]

What i've got is an array that looks something like
1001000100
0001111101
1111100111
1111010010
0010100001
1100111111
1111010110
1111110111
1111011010
1111101110
I need to be able to calculate quickly whether or not there is a path of 1s through the array by travelling from one cell to another, either horizontally, vertically or diagonally. In other words I need a constant path of 1s from the left of the array to the right. I tried using if statements like
if (array[x][y] && array[x+1][y] etc ==1)
but because of the number of possible paths, the number of if statements required is huge. Is there a quick method? I've racked my brains for a for loop method but cant seem to be able to think of one.
Thanks

[Ganon11]

You could use recursion. For example:

You have arrived at some place in the matrix, matrix[X][Y]. You know there is a path from matrix[X][Y] to the right edge if there is a path from any of the surrounding one's of matrix[X][Y] (that is, matrix[X-1][Y-1], matrix[X][Y-1], matrix[X+1][Y-1], matrix[X-1][Y], etc.)

You have successfully found a path if matrix[X][Y] is already on the right edge.

There's some extra detail work you have to do, such as making sure you don't infinitely recurse and deciding how to call the function initially, but this should get you started.

[Ganon11]

Please don't double post - that is, please don't create a new thread to answer the same question. In addition, I have changed the title of the thread to something a little more descriptive of the specific issue you're addressing.

MODERATOR