a mouse is trapped in a labyrinth.. and he has to find the cheese!
the input is W and H (height and width), and a graph like this one:

``````##...#
C###..
......
.####.
.....M``````

i'm supposed to calculate the shortest amount of steps he needs to make to get to the cheese (C).
also if he cannot get to the cheese you gotta print "impossible"...
while i 've found a way to flood-fill the map to find if it's even possible to get to the cheese, i still can't find a good algorithm to find the shortest path. i've read about those shortest path things but i kinda don't get it... help!!! pleaseee :).

## All 18 Replies

assuming your map isn't too huge, couldn't this be solved by:

1) find a path to the cheese, set to 'shortest'
2) find another (unique) path to cheese, test for 'shorter than current shortest'
3) update 'shortest' as needed
4) terminate after no new paths are possible

depending on map size and processor speed this shouldn't take too long... but there are lots of other (more complex, and elegant) ways to find shortest path.

As far as unweighted graphs are concerned, a bfs should suffice to find the shortest path between two nodes. It should probably look something like:

``````procedure bfs(Graph, source, dest)
enqueue source
set pi[source] = NIL
seen[source] = true

while queue is not empty do
pop an item from queue
for each neighbour of popped item
if neighbour is accessible and not seen yet
pi[neighbour] = popped item
seen[neighbour] = true;
enqueue neighbour

distance = 0
cur = dest
while cur != source do
cur = pi[cur]
dist = dist + 1
return dist``````

Alot of programmers think logical and selective searching methods work the best. But bruteforce is recomendable in situations like this. Just have the computer brute force every possible path (with an array) to the cheese, and keep track of the number of moves for each one. Then have a loop to find the shortest of the group. I think I'll try and write the code and I'll post it if I do.

hmm, but trying all the possible paths would still require flood-filling at every step to check where to turn, wouldn't it? I mean.. otherwise you could get to a dead end.

Like ruggedrat said, a breadth first search will suffice. Starting at M, mark each reachable node as distance 1; from those nodes, mark each reachable node that has not already been visited as distance 2; etc:

``````##765#
C###43
765432
6####1
54321M``````

The shortest path is 8.

okkkkay...so i tried... and failed. my code looks pretty fine to me (the numbering thing).
could someone please take a look? thanks!

``````#include <cstdio>
#include <cstring>
#define MAX 100

using namespace std;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
int X, Y;
char map[ MAX ][ MAX ];

void bfs( int x, int y )
{
for( int d = 0; d < 4; ++d )
if( map[x+dx[d]][y+dy[d]] == '.' )
map[x+dx[d]][y+dy[d]] = char( int( map[x][y] ) + 1 );
}

int main( void )
{
scanf( "%d%d", &X, &Y );
for( int i = 0; i < X; ++i )
scanf( "%s", map[i] );
for( int i = 0; i < X; ++i )
for( int j = 0; j < Y; ++i )
if( map[i][j] == 'M' )
for( int d = 0; d < 4; ++d )
if( map[i+dx[d]][j+dy[d]] == '.' )
map[i+dx[d]][j+dy[d]] = '1';

for( int num = 1; num <= X*Y; ++num ) {
for( int i = 0; i < X; ++i )
for( int j = 0; j < Y; ++j )
if( map[i][j] == char( num + 48 ) )
bfs( i, j );
}
for( int i = 0; i < X; ++i ){
for( int j = 0; j < Y; ++i )
printf( "%c", map[i][j] );
printf( "\n" );
}
scanf( "\n" );
return 0;
}``````

Hmmm I've been thinking about this for a while. I'm too lazy to write the code at the moment. But you could have it brute force (ie always move left, if can't move up, if cant move down, if can't move right). Then save the locations of every instance where there's multiple paths possible, and also save the amount of steps to that point. If and when the algorithm runs into a dead end, revert back to the last desicive point.

Also, you should save each step taken to ensure that the mouse doesn't backtrack and waste steps. Alot of arrays, and possibly alot of memory depending on the size of the maze might be needed.

okkkkay...so i tried... and failed. my code looks pretty fine to me (the numbering thing).
could someone please take a look? thanks!

``````// check:
for( int i = 0; i < X; ++i ){
for( int j = 0; j < Y; ++i )``````

You've got this sequence twice in your code - it's wrong both times. Also, you should check whether the map location exists before you access it - e.g. map[-1][-1] is not actually in the map[][] variable (you may overwrite data in another variable or segfault).

your code works otherwise; well done.

okay, so now i've fixed the range between 0 and X and 0 and Y, still reports an error! not a compiling error but some stupid windows bug. still don't know what's wrong with my for loops...
i changed the increment operators...works the same.

``````#include <cstdio>
#include <cstring>
#define MAX 100

using namespace std;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
int X, Y;
char map[ MAX ][ MAX ];

void bfs( int x, int y )
{
for( int d = 0; d < 4; ++d )
if( map[x+dx[d]][y+dy[d]] == '.'&&x+dx[d]>0&&y+dy[d]>0&&x+dx[d]<X&&y+dy[d]<Y )
map[x+dx[d]][y+dy[d]] = char( int( map[x][y] ) + 1 );
}

int main( void )
{
scanf( "%d%d\n", &X, &Y );
for( int i = 0; i < X; ++i )
scanf( "%s", map[i] );
for( int i = 0; i < X; i++ )
for( int j = 0; j < Y; i++ )
if( map[i][j] == 'M' )
for( int d = 0; d < 4; ++d )
if( map[i+dx[d]][j+dy[d]] == '.'&&i+dx[d]>0&&j+dy[d]>0&&i+dx[d]<X&&j+dy[d]<Y )
map[i+dx[d]][j+dy[d]] = '1';

for( int num = 1; num <= X*Y; ++num ) {
for( int i = 0; i < X; i++ )
for( int j = 0; j < Y; j++ )
if( map[i][j] == char( num + 48 ) )
bfs( i, j );
}
for( int i = 0; i < X; i++ ){
for( int j = 0; j < Y; i++ )
printf( "%c", map[i][j] );
printf( "\n" );
}
scanf( "\n" );
return 0;
}``````

I'll be more specific:
// check: `for( int j = 0; j < Y; ++i )` or even what you've changed it to `for( int j = 0; j < Y; i++ )` for that matter.

hint: (try incrementing j, not i in that statement)

looool, i can't belive it :p
happens to me all the time, i didn't see it, thanks!!

So is this thread solved then? Haha...Because I've spent the last few hours trying to write a solution :P . I'm a bit rusty with my linked lists, so it could take a bit longer. I'll post regardless when I'm finished.

Well here's what I got so far. It's pretty large, but that's just me trying to keep it robust enough to handly any size maps. It's not in any working order, I'm still debugging it. When I'm done I'll add some comments too. Just hoping someone would help me debug it :P

``````#include<iostream>
#include<iomanip>
#include<fstream>
#include<crtdbg.h>
using namespace std;

const int X_MAX = 7;
const int Y_MAX = 6;

struct Grid
{
char _Plot[X_MAX][Y_MAX];
int  _XCheese;
int  _YCheese;
int  _XMouse;
int  _YMouse;
};

struct Data
{
int _X;
int _Y;
int _iDistance;
};

struct SNode
{
Data    _DATA;
SNode*  m_pNext;
int		m_iFreq;
};

void AddNode(SNode* &, Data);
void MakeGrid(Grid &, char []);
void DeleteList(SNode* &);
bool CheckPoint(int, int, Grid &, SNode* &);
bool FindPath(Grid &);
int  CheckRoutes(Grid &, SNode* &);
int main()
{
//memory leak detection
_CrtSetDbgFlag (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

Grid Gridplot;
MakeGrid(Gridplot, "Grid2.txt");
//	cout << "Mouse  X-Y: " << Gridplot._XMouse + 1 << " , " << Gridplot._YMouse + 1;
//	cout << "\nCheese X-Y: " << Gridplot._XCheese + 1<< " , " << Gridplot._YCheese + 1;
cout << endl << "Found: " << (FindPath (Gridplot) ? "Yes" : "No");
cin.ignore(cin.rdbuf()->in_avail());
cin.get();
return 0;
}

{
SNode* pNew = 0;				//the new node to add

SNode* pCurrent = 0;			//the node 'cursor' - the
//current node being analyzed

pCurrent = pHead;				//start looking at the head of the list

//if the head doesnt exist yet, make one...
{
//the reason why pNew isnt allocated at the start of the function, is
//that a new node isn't always created in this function

pNew = new(nothrow) SNode;	//new dynamically allocated memory for a node
pNew->_DATA = DATA;		//set the data of the node to iData
pNew->m_pNext = 0;			//since its the head, next node is null
pNew->m_iFreq = 1;			//starts with a frequency of 1
pHead = pNew;				//finally, set the head to the new node
}

//but if there is a head...
else
{
//as long as there's a next node to go to, traverse the list
//until the node before the target node is found

while(pCurrent->m_pNext)
pCurrent = pCurrent->m_pNext;
pNew = new(nothrow) SNode;
pNew->_DATA = DATA;
pNew->m_iFreq = 1;
pNew->m_pNext = pCurrent->m_pNext;
pCurrent->m_pNext = pNew;
}

return;
}

{
SNode* pDelete;						//used as a swapper during the delete
SNode* pCurrent;					//the list cursor
pCurrent = pHead;					//make it start at the head

//traverse the list and delete everything!
while (pCurrent)
{
pDelete = pCurrent;				//set the swapper as the current node
pCurrent = pCurrent->m_pNext;   //go to the next node
delete pDelete;					//delete the original node
}
return;
}

void MakeGrid(Grid &Gridplot, char Filename[])
{
ifstream InFile;
InFile.open(Filename);
char cBuffer = 0;

for (int i = 0; i < Y_MAX; i++)
{
for (int ii = 0; ii < X_MAX; ii++)
{
if (InFile.eof() != true)
{
InFile.get(cBuffer);
if (cBuffer == 'C')
{
Gridplot._XCheese = ii;
Gridplot._YCheese = i;
}
else if (cBuffer == 'M')
{
Gridplot._XMouse = ii;
Gridplot._YMouse = i;
}
Gridplot._Plot[ii][i] = cBuffer;
cout << cBuffer;
}
}
cout << endl;
}
InFile.close();

return;
}

bool FindPath(Grid &Gridplot)
{
bool Possible = false;
bool AllDead = false;
int iCursorX = 0,
iCursorY = 0,
iRoute =  0,
i	   =  0;

SNode* Cursor = {0};
SNode* pCurrent = {0};
Data   Buffer = {0};
Data   Current = {0};
Buffer._X = Gridplot._XMouse;
Buffer._Y = Gridplot._YMouse;
Buffer._iDistance = 0;
for (int iSet = 0; iSet < 100; iSet++)
{
}
{
for (i = 0; i <= iRoute; i++)
{
{
pCurrent = Cursor[i];
while(pCurrent->m_pNext)
pCurrent = pCurrent->m_pNext;
Current = pCurrent->_DATA;
cout << endl << "Cursor X-Y: " << Current._X << " , " << Current._Y << "   Routes Available: " << CheckRoutes(Gridplot, Cursor[i]);
if (CheckRoutes(Gridplot, Cursor[i]) > 1)		//if there is multiple paths, split in 2
{
cout << "\nMouse Path Was Split: ";
if (CheckPoint(Current._X + 1,Current._Y, Gridplot, Cursor[i]))
{
cout << "RIGHT To Route #:" << i << endl;
iRoute++;
Buffer._X = Current._X + 1;
Buffer._iDistance = Current._iDistance + 1;
}
else if (CheckPoint(Current._X - 1,Current._Y, Gridplot, Cursor[i]))
{
cout << "LEFT To Route #:" << i << endl;
iRoute++;
Buffer._X = Current._X - 1;
Buffer._iDistance = Current._iDistance + 1;
}
else if (CheckPoint(Current._X,Current._Y - 1, Gridplot, Cursor[i]))
{
cout << "UP To Route #:" << i << endl;
iRoute++;
Buffer._Y = Current._Y - 1;
Buffer._iDistance = Current._iDistance + 1;
}
else if (CheckPoint(Current._X,Current._Y + 1, Gridplot, Cursor[i]))
{
cout << "DOWN To Route #:" << i << endl;
iRoute++;
Buffer._Y = Current._Y + 1;
Buffer._iDistance = Current._iDistance + 1;
}

}
else if (CheckRoutes(Gridplot, Cursor[i]) == 1) //for moving without adding a new route
{
if (CheckPoint(Current._X + 1,Current._Y, Gridplot, Cursor[i]))
{
cout << "\nRIGHT! " << i;
Buffer._X = Current._X + 1;
Buffer._Y = Current._Y;
Buffer._iDistance = Current._iDistance + 1;
}
else if (CheckPoint(Current._X - 1,Current._Y, Gridplot, Cursor[i]))
{
cout << "\nLEFT! " << i;
Buffer._X = Current._X - 1;
Buffer._Y = Current._Y;
Buffer._iDistance = Current._iDistance + 1;
}
else if (CheckPoint(Current._X,Current._Y - 1, Gridplot, Cursor[i]))
{
cout << "\nUP! " << i;
Buffer._X = Current._X ;
Buffer._Y = Current._Y - 1;
Buffer._iDistance = Current._iDistance + 1;
}
else// if (CheckPoint(Current._X,Current._Y + 1, Gridplot, Cursor[i]))
{
cout << "\nDOWN! " << i;
Buffer._X = Current._X;
Buffer._Y = Current._Y + 1;
Buffer._iDistance = Current._iDistance + 1;
}
}
else
}

}

for (i = 0; i < iRoute; i++)
};
for (i = 0; i < 1000; i++)
DeleteList(Cursor[i]);
return Possible;
}

int CheckRoutes(Grid &Gridplot, SNode* &Cursor)
{
int iRoutes = 0;
if (CheckPoint(Cursor->_DATA._X + 1,Cursor->_DATA._Y, Gridplot, Cursor))
iRoutes++;
if (CheckPoint(Cursor->_DATA._X - 1,Cursor->_DATA._Y, Gridplot, Cursor))
iRoutes++;
if (CheckPoint(Cursor->_DATA._X,Cursor->_DATA._Y - 1, Gridplot, Cursor))
iRoutes++;
if (CheckPoint(Cursor->_DATA._X,Cursor->_DATA._Y + 1, Gridplot, Cursor))
iRoutes++;
return iRoutes;
}

bool CheckPoint(int CursorX, int CursorY, Grid &Gridplot, SNode* &pHead)
{
bool Return = false;
SNode* pCurrent = pHead;
if (Gridplot._Plot[CursorX][CursorY] == '.' || Gridplot._Plot[CursorX][CursorY] == 'C')
Return = true;
if (Gridplot._Plot[CursorX][CursorY] == 'M')
Return = false;
while(pCurrent->m_pNext)
{
if (CursorX == pCurrent->_DATA._X && CursorY == pCurrent->_DATA._Y)
Return = false;
pCurrent = pCurrent->m_pNext;
}

return Return;
}``````

whoa, that's some chunk of code! Well it did display the matrix after fixing the ++i's but no numbers were showin... i'd love to help you debug it...but i'm a bit lost there...

Haha yeah it's a bit short on the comments. And the spacing got all screwed up.

Anyway I'm having some weird problems with this, but it's definatly a fun challenge...to such a simple seeming problem...

Okay...now i got what you really meant by numbering the steps...
i made a matrix for visited points and numbered them...i used queues, they are perfect for this, also saw them in other bfs explanations...so...here's my code (also, please check if it could be improved in some way!):

``````#include <cstdio>
#include <cstring>
#include <queue>
#define MAX 200

using namespace std;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
int X, Y, v[ MAX ][ MAX ];
char map[ MAX ][ MAX ];
int best = 0;

void bfs( int x, int y )
{
queue<int> qx, qy;
qx.push( x ); qy.push( y );
v[x][y] = 1;

while( !qx.empty() )
{
int x = qx.front(); qx.pop();
int y = qy.front(); qy.pop();
for( int d = 0; d < 4; ++d ) {
int nx = x + dx[d], ny = y + dy[d];
if( nx < 0 || ny < 0 || nx >= X || ny >= Y || map[nx][ny] == '#' || v[nx][ny] != 0 )
continue;

qx.push( nx ); qy.push( ny );
v[nx][ny] = v[x][y]+1;
}
}
}

int main( void )
{
memset( v, 0, sizeof v );
scanf( "%d%d", &X, &Y );
for( int i = 0; i < X; ++i )
scanf( "%s", map[i] );
for( int i = 0; i < X; ++i )
for( int j = 0; j < Y; ++j )
if( map[i][j] == 'M' )
bfs( i, j );

int x, y;
for( int i = 0; i < X; ++i )
for( int j = 0; j < Y; ++j )
if( map[i][j] == 'C' ) {
x = i, y = j;
}
bool noway = true;
for( int d = 0; d < 4; ++d ) {
int xx = x + dx[d], yy = y + dy[d];
if( v[xx][yy] != 0 && xx >= 0 && yy >= 0 && xx < X && yy < Y ) {
noway = false;
if( v[xx][yy] > best )best = v[xx][yy];
}
}
/* THIS IS JUST IN CASE YOU WANNA PRINT THE STEP NUMBERS
for( int i = 0; i < X; ++i ) {
for( int j = 0; j < Y; ++j )
printf( "%d  ", v[i][j] );
printf( "\n" );
}*/

if( noway )printf( "NO WAY!!\n" );
else printf( "%d\n", best );
scanf( "\n" );
return 0;
}``````

oops...it's dfs actually...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.