Tuxdude
BAN USERAll the possible movement lines of the Bishops on the board can be described by 2 set of lines, namely:
y = x + c1
y = -x + c2
We have 2 points (x1, y1) i.e. start and (x2, y2) i.e. end
I've given a pseudocode, assuming there are no pieces which could block the shortest path.
// First ensure there is an actual bishop bath between the 2 points
// If the diff between the x coordinates is even, the diff between the
// y coordinates must also be even, or both should be odd.
// It cannot be a mix
bool xdiffeven = (| x1 - x2 | % 2 == 0)
bool ydiffeven = (| y1 - y2 | % 2 == 0)
if (xdiffeven != ydiffeven)
{
return ERROR_MOVE_NOT_POSSIBLE
}
else if ((y1 - x1) == (y2 - x2) || (y1 + x1) == (y2 + x2))
{
// We have a direct line connecting the 2 points.
// We only need to figure if there are any other pieces which may be in this path
}
else
{
// We can get from A(x1,y1) to B(x2,y2) using 2 possible paths, each in 2 moves
// We determine the intermediate point next
// The 2 points can be found at the intersection of the following pair of lines:
// y = x + c1A and y = -x + c2B
// y = -x + c2A and y = x + c1B
// For y = x + c1A and y = -x + c2B
x = ((y2 + x2) - (y1 - x1))/2
y = (y2 + x2) - x
// For y = -x + c2A and y = x + c1B
x = ((y2 - x2) - (y1 + x1)) / 2
y = x + (y1 + x1)
}
This logic could be extended to figure out a path around a piece which could block the path, but the problem then gets recursive to do the same for the sub-path which could again have pieces in the way.
- Tuxdude June 15, 2013
You should also compare the length of the lists.
- Tuxdude June 16, 2013In addition, this algorithm would not work especially if the elements can be 0 or negative. Example:
[1 0 1]
[2 0 0]
[-1 0 -1]