Recursive algoritme for finding the shortest path

[Jochus]

"Karl Heinz Buchegger" schreef:

Study it. The function is only 17 lines long (excluding comments).
There are *4* recursive calls!

This is the solution (well, allmost ...)

----

#include <iostream>

#include <ctime>

#include <cstdlib>

#include <iomanip>

//#define DEBUG

using namespace std;

const int DIM=10;

const int EIND=0;

const int MUUR=-1;

const int WEG=-2;

const int PAD=-3;

const int MIN=10;

const int MAX=60;

const int delta[4][2]= { {-1,0 } , {1,0} , {0,-1 } , {0,1} };

int lees_aantal_doolhoven() {

int run;

cin >> run;

while ( run < 0)

cin >> run;

return run;

}

void inlezen_speelveld (int matrix[][DIM], int dimensie, int &beginx, int
&beginy) {

for (int r=0; r < dimensie; r++) {

for (int k=0; k < dimensie; k++) {

cin >> matrix[r][k];

if ( matrix[r][k] == 0) {

beginx=r;

beginy=k;

}

}

}

}


bool binnen_veld (int xx, int yy, int dimensie) {

bool controle=false;

if (xx >= 0 && xx < dimensie && yy >= 0 && yy < dimensie)

controle=true;

return controle;

}

void kort(int matrix[][DIM], int dimensie, int x, int y) {

for (int i = 0; i < 4; i ++) {

int xx = x + delta[0];

int yy = y + delta[1];

if ( binnen_veld(xx,yy,dimensie) ) {

int t = matrix[x][y] + 1;

if (matrix[xx][yy] == -2 || (matrix[xx][yy] > 0
|| matrix[xx][yy] < matrix[x][y])) {

matrix[xx][yy] = t;

kort(matrix,dimensie, xx,
yy);

}

}

}

}

void uitschrijven(int matrix[][DIM], int dimensie) {

for (int r=0; r < dimensie; r++) {

for (int k=0; k < dimensie; k++)

cout << setw(3) << matrix[r][k];

cout << endl;

}

cout << endl;

}


int main () {

int run=lees_aantal_doolhoven();

cout << run << endl;

srand(time(NULL));


for (int i=0; i < run; i++) {

// dimensie is?

int dimensie;

cin >> dimensie;

cout << "dim:" << dimensie << endl;

// inlezen speelveld;

int matrix[DIM][DIM];

int beginx, beginy;

inlezen_speelveld(matrix,dimensie,beginx,beginy);


// kortste weg?

kort(matrix,dimensie,beginx,beginy);

// uitschrijven afstandenmatrix

uitschrijven(matrix,dimensie);

}

return 0;

}