Shortest path kind of problem...

[gregorynoob]

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 :).

[ivailosp]

my old program - it only search for path, but not short
http://www.dev-spot.com/forums/index.php?topic=57.msg309#msg309

[ninjaneer]

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.

[ruggedrat]

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

[skatamatic]

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.

[gregorynoob]

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.

[titaniumdecoy]

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.

[gregorynoob]

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;
}

[skatamatic]

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.

[dougy83]

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.

[gregorynoob]

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;
}

[dougy83]

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)

[gregorynoob]

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

[skatamatic]

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.

[skatamatic]

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;
	bool _DeadEnd;
};

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

struct SNode
{
	Data    _DATA;
	bool    _DeadEnd;
	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;
}

void AddNode(SNode* &pHead, Data DATA)
{
		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...
		if(pHead == 0)		
		{
			//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;
}

void DeleteList(SNode* &pHead)
{	
	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[100] = {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++)
	{
		AddNode(Cursor[iSet], Buffer);
		Cursor[iSet]->_DeadEnd = false;
	}
	while (!AllDead)
	{
		for (i = 0; i <= iRoute; i++)
		{
			while (!Cursor[i]->_DeadEnd)
			{
				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;
						AddNode(Cursor[iRoute], Buffer);
					}
					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;
						AddNode(Cursor[iRoute], Buffer);
					}
					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;
						AddNode(Cursor[iRoute], Buffer);
					}
					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;
						AddNode(Cursor[iRoute], Buffer);
					}

				}
				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;
						AddNode(Cursor[i], Buffer);
					}
					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;
						AddNode(Cursor[i], Buffer);
					}
					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;
						AddNode(Cursor[i], Buffer);
					}
					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;
						AddNode(Cursor[i], Buffer);
					}
				}
				else
					Cursor[i]->_DeadEnd = true;
			}

		}

		AllDead = true;
		for (i = 0; i < iRoute; i++)
			if (!Cursor[i]->_DeadEnd)
				AllDead = false;
	};
	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;
		if(pHead != 0)		
			while(pCurrent->m_pNext)
			{
				if (CursorX == pCurrent->_DATA._X && CursorY == pCurrent->_DATA._Y)
					Return = false;
				pCurrent = pCurrent->m_pNext;
			}
		
	return Return;
}

[gregorynoob]

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...

[skatamatic]

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...

[gregorynoob]

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;
}

[gregorynoob]

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