You have a map of the territories of three countries:

*R*,

*G*,

*B*.

*R*is represented by 1,

*G*by 2,

*B*by 3, and 0 means water. Here's an example of a map:

Quote

0110313

3333000

2033000

2203011

2000010

We say two elements of the map-matrix are

**neighbors**if they have the same value and if they are consecutive on a line or a column. For example the three 1-s in the lower right corner of the matrix are "neighbors".

In a certain part of the program I have to write an algorithm to determine whether or not it is possible to build a bridge between two given points, and if so, return its length. A bridge is 'buildable' if it meets these conditions:

- It must begin from a point filled with water that is next to the beginning point;
- It must end in a point filled with water that is next to the ending point;
- Any two consecutive elements of the bridge must be neighbors;
- All elements of the bridge must be above an area covered by water.

Quote

01103

**1**3

3333000

2033000

2203011

**2**000010

Here's how I've done it. I'm curious as to how others would have approached this problem.

int Progress(int, int); int BridgeLength(int y1, int x1, int y2, int x2, string* map) { /* 'y1' and 'x1' are the coordinates of the starting point, 'y2' and 'x2' are the coordinates of the ending point. */ // Wiil return 0 if bridge is impossible. // First it has to be determined how to progress on the // X and Y axis in order to get from (x1, y1) to (x2, y2). const int prog_x = Progress(x1, x2); const int prog_y = Progress(y1, y2); int bridge = 0; while (true) { int impossible = 0; // THE X AXIS if (x1 != x2) { char ch = map[y1][x1+prog_x]; if (ch == '0') { x1 += prog_x; bridge++; } else if ((x1 + prog_x == x2) && (y1 == y2)) { break; } else { impossible++; } } else impossible++; // THE Y AXIS if (y1 != y2) { char ch = map[y1+prog_y][x1]; if (ch == '0') { y1 += prog_y; bridge++; } else if ((y1 + prog_y == y2) && (x1 == x2)) { break; } else { impossible++; } } else impossible++; // if we failed to move on both the x and the y axis // it means the bridge is impossible to build if (impossible == 2) { bridge = 0; break; } } return bridge; } int Progress(int p1, int p2) { int prog; if (p1 > p2) prog = -1; else if (p1 < p2) prog = 1; else if (p1 == p2) prog = 0; return prog; }

(My first try was even uglier.)

This post has been edited by **diego_pmc**: 05 November 2009 - 12:32 PM