C++ Matrix, can Popeye get to Olive

[pork95]

There is char matrix A with M rows and N colums. Elements of that matrix are "#"(walls) and "."(roads), P(Popeye) and O(Olive). Example:

#.......#.
#..####.#O
#P...#..#.
##...#..#.
######.... 

I need to write a C++ code to check if there is a road that Popeye can walk to get to Olive. He can walk up, down, left and right (he can't jump over walls).
For a result i need to cout yes or no.

Any ideas?

[lastchance]

It looks like a graph theory problem. You need the set of nodes that are connected to the first node P. If Olive is in that set then the sailor gets his girl.

One possible algorithm:
- start with all nodes 'unticked'
- start with P and tick off all nodes it can reach (ie there is a "." road)
- for all ticked nodes, tick off any nodes that they can reach
And so on.
Stop when there is no possibility of ticking more ... failure ... or Olive is caught ... "success".

You can, of course, see that all ends happily in this example!

[pork95]

I'm stuck and I need help for this path function ( and other functions :D ) :)

#include <iostream>
using namespace std;
#define M 5
#define N 10

bool solve(char A[M][N], int p1, int p2);
bool path(char A[M][N], int p1, int p2);

bool safe(char A[M][N], int p1, int p2) {
	if (p1 >= 0 && p1 < M && p1 < N && p2 >= 0 && p2 < M && p2 < N && A[p1][p2] == '.') {
		return true;
	}
	return false;
}

int main() {
	int p1, p2;
	char A[M][N] = { { '#', '.', '.', '.', '.', '.', '.', '.', '#', '.' },
					{ '#', '.', '.', '#', '#', '#', '#', '.', '#', 'O' },
					{ '#', 'P', '.', '.', '.', '#', '.', '.', '#', '.' },
					{ '#', '#', '.', '.', '.', '#', '.', '.', '#', '.' },
					{ '#', '#', '#', '#', '#', '#', '.', '.', '.', '.' } };


	//looking for popeye.
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (A[i][j] == 'P') { p1 = i; p2 = j; break; }
		}
	}

	solve(A, p1, p2);

	return 0;
}

bool solve(char A[M][N], int p1, int p2) {

	if (path(A, p1, p2) == false) {
		cout << "NO" << endl;
	}
	return true;
}

bool path(char A[M][N], int p1, int p2) {

	if (A[p1][p2] == 'O') {
		cout << "YES" << endl;
		return true;
	}

		if (safe(A, p1, p2) == true) {
			if (path(A, p1 + 1, p2) == true)  
				return true;


			if (path(A, p1 - 1, p2) == true)  
				return true; 


			if (path(A, p1, p2 + 1) == true) 
				return true;


			if (path(A, p1, p2 - 1) == true) 
				return true; 
			
	}
	return false;
}

[AbstractionAnon]

Line 10: Why are you testing p1 < N? p1 is Popeye's vertical position (row). There is no connection between his vertical position and the number of columns (N).

Likewise, why are you testing p2 < M? p2 is Popeye's horizontal position. There is no connection between his horizontal position and the number of rows (M).

[pork95]

bool safe(char A[M][N], int p1, int p2) {
	if (p1 >= 0 && p1 < M && p2 >= 0 && p2 < N && A[p1][p2] == '.') {
		return true;
	}
	return false;
}

like this? what should i do now to make it print yes?

[AbstractionAnon]

like this?

Yes.

what should i do now to make it print yes?

Line 32: You call solve() with Popeye's initial location, which calls path().

Line 52: path() calls safe() with Popeye's initial location, but safe() does not consider a "P' to be a valid location and returns false, thereby exiting safe() and path() with false on the very first call.

Your program is going to be susceptible to a stack overflow as you do not keep track of cells that you have visited. Therefore you will likely have infinite recursion as every valid path from every cell will be explored at every level of recursion.

Please use

[code]

tags, not

[quote]

tags.