C++中简单的寻路问题，求指点

Question

读取txt中的迷宫，并读取起始点坐标和目标点坐标进行寻路，这是我的代码：
#include

#include <fstream>

#include <sstream>


using namespace std;


struct Move

{

    int x;
      int y;

}Move[1000];


int Maze(string name,int sx,int sy,int gx,int gy);


int main(int nargs, char *argv[])

{

  string name = argv[1];
    int sx = stoul(string(argv[2]));

  int sy = stoul(string(argv[3]));

  int gx = stoul(string(argv[4]));

  int gy = stoul(string(argv[5]));


  Maze(name,sx,sy,gx,gy);   


  cout<<endl;

}


int Maze(string name,int sx,int sy,int gx,int gy)

{   


  ifstream read(name);

  int a[2]; 


//read the size of the maze and create an array to store it 

  for(int i=0;i<2;i++)

  {

    read>>a[i];

  }


  int row = a[0];

  int col = a[1];

  int maze[row][col];


  for(int i=0;i<row;i++)

  { 

    for(int j=0;j<col;j++)

  {   

    read>>maze[i][j];

   }

  }  

/*for(int i=0;i<row;i++)

{

for(int j=0;j<col;j++)

{

cout<<map[i][j]<<" ";

}

cout<<endl;

}*/

read.close();


if(maze[sx][sy]==1||maze[gx][gy]==1)

{

  cout<<"Error place!"<<endl;

}


  else if(maze[sx+1][sy]==1&&maze[sx][sy+1]==1&&maze[sx-1][sy]==1&&maze[sx][sy-1]==1)

{

  cout<<"No paths to go!"<<endl;

}


  else

{

  Move[0].x = sx;

  Move[0].y = sy;

  int i = 1;

  while(Move[0].x!=gx && Move[0].y!=gy)

{


if(maze[sx+1][sy]==0)

{

Move[0].x = Move[0].x+1;

cout<<"D"<<" ";

continue;               

}


else if(maze[sx-1][sy]==0)

{

Move[0].x = Move[0].x-1;

cout<<"U"<<" "; 

continue;           

}


else if(maze[sx][sy+1]==0)

{

Move[0].y = Move[0].y+1;

cout<<"R"<<" ";     

continue;       

}


else if(maze[sx][sy-1]==0)

{

Move[0].y = Move[0].y-1;

cout<<"L"<<" "; 

continue;           

   }

 }

}

}
一旦走进死胡头就没法继续了
同时我也想用递归的方法来解决但不知道怎么下手，求各位指点。

Answer 1

$ cat maze.cpp
#include
#include
#include
#include

using namespace std;

int gx;
int gy;

int *maze;
int rows;
int cols;

#define MAZE(x, y) maze[cols*(x)+(y)]

int initMaze(const char *name, int **maze, int *rows, int *cols)
{

ifstream ifs(name);

ifs >> *rows;
ifs >> *cols;

*maze = new int[*rows * *cols];

for (int i = 0; i < *rows; i++)
{ 
    for (int j = 0; j < *cols; j++)
    {   
        ifs >> (*maze)[*cols*i+j];
    }
}  

if (!ifs)
{
   cout << "Error reading " << name << endl;
   return -1;
}

ifs.close();

return 0;

}

bool checkMaze(int *maze, int rows, int cols, int sx, int sy, int gx, int gy)
{
for (int i = 0; i < rows * cols; i++)
{
cout << maze[i] << " ";
}

cout << endl << endl;

for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < cols; j++)
    {
        cout << MAZE(i, j) << " ";
    }

    cout << endl;
}

if (sx < 0 || sy < 0 || gx < 0 || gy < 0
    || sx >= rows || sy >= cols || gx >= rows || gy >= cols)
{
    cout << "Error (x, y)" << endl;
    return false;
}

if (MAZE(sx, sy) != 0 || MAZE(gx, gy) != 0)
{
    cout << "Error place!" << endl;
    return false;
}

return true;

}

bool walkUp(int x, int y);
bool walkDown(int x, int y);
bool walkLeft(int x, int y);
bool walkRight(int x, int y);

void findExit(int x, int y)
{
cout << "(" << x+1 << ", " << y+1 << ") --> (" << gx+1 << ", " << gy+1 << ")" << endl << endl;

cout << "(" << x+1 << ", " << y+1 << ") ";
if (x == gx && y == gy
    || walkDown(x+1, y)
    || walkUp(x-1, y)
    || walkRight(x, y+1)
    || walkLeft(x, y-1))
{
    cout << endl;
    cout << "Done!" << endl;
    return;
}

cout << endl;
cout << "Lost!" << endl;

}

bool walkUp(int x, int y)
{
if (x < 0) return false;
if (MAZE(x, y) != 0) return false;

cout << "U(" << x+1 << "," << y+1 << ") ";

if (x-1 == gx && y == gy)
{
    cout << "U(" << x << "," << y+1 << ") ";
    return true;
}

if (x == gx && y+1 == gy)
{
    cout << "R(" << x+1 << "," << y+2 << ") ";
    return true;
}

if (x == gx && y-1 == gy)
{
    cout << "L(" << x+1 << "," << y << ") ";
    return true;
}

if (walkUp(x-1, y)
    || walkRight(x, y+1)
    || walkLeft(x, y-1))
{
    return true;
}

cout << "D(" << x+2 << "," << y+1 << ") ";
return false;

}

bool walkDown(int x, int y)
{
if (x >= rows) return false;
if (MAZE(x, y) != 0) return false;

cout << "D(" << x+1 << "," << y+1 << ") ";

if (x+1 == gx && y == gy)
{
    cout << "D(" << x+2 << "," << y+1 << ") ";
    return true;
}

if (x == gx && y+1 == gy)
{
    cout << "R(" << x+1 << "," << y+2 << ") ";
    return true;
}

if (x == gx && y-1 == gy)
{
    cout << "L(" << x+1 << "," << y << ") ";
    return true;
}

if (walkDown(x+1, y)
    || walkRight(x, y+1)
    || walkLeft(x, y-1))
{
    return true;
}

cout << "U(" << x << "," << y+1 << ") ";
return false;

}

bool walkLeft(int x, int y)
{
if (y < 0) return false;
if (MAZE(x, y) != 0) return false;

cout << "L(" << x+1 << "," << y+1 << ") ";

if (x == gx && y-1 == gy)
{
    cout << "L(" << x+1 << "," << y << ") ";
    return true;
}

if (x-1 == gx && y == gy)
{
    cout << "U(" << x << "," << y+1 << ") ";
    return true;
}   

if (x+1 == gx && y == gy)
{
    cout << "D(" << x+2 << "," << y+1 << ") ";
    return true;
}

if (walkLeft(x, y-1)
    || walkUp(x-1, y)
    || walkDown(x+1, y))
{
    return true;
}

cout << "R(" << x+1 << "," << y+2 << ") ";
return false;

}

bool walkRight(int x, int y)
{
if (y >= cols) return false;
if (MAZE(x, y) != 0) return false;

cout << "R(" << x+1 << "," << y+1 << ") ";

if (x == gx && y+1 == gy)
{
    cout << "R(" << x+1 << "," << y+2 << ") ";
    return true;
}

if (x-1 == gx && y == gy)
{
    cout << "U(" << x << "," << y+1 << ") ";
    return true;
}

if (x+1 == gx && y == gy)
{
    cout << "D(" << x+2 << "," << y+1 << ") ";
    return true;
}

if (walkRight(x, y+1)
    || walkUp(x-1, y)
    || walkDown(x+1, y))
{
    return true;
}

cout << "L(" << x+1 << "," << y << ") ";
return false;

}

int main(int argc, char * const argv[])
{
if (argc != 6)
{
cout << "Usage: " << argv[0] << "MazeMapFile entranceX entranceY exitX exitY" << endl;
return 1;
}

int sx = atoi(argv[2]) - 1;
int sy = atoi(argv[3]) - 1;

gx = atoi(argv[4]) - 1;
gy = atoi(argv[5]) - 1;

if (initMaze(argv[1], &maze, &rows, &cols) != 0
    || !checkMaze(maze, rows, cols, sx, sy, gx, gy))
{
    return 2;
}

cout << endl;

findExit(sx, sy);

cout << endl;
return 0;

}

$ cat maze.txt
4 4
1 0 0 1
0 1 0 0
0 0 0 1
1 0 1 0

$ maze maze.txt 1 2 4 2
1 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0

1 0 0 1
0 1 0 0
0 0 0 1
1 0 1 0

(1, 2) --> (4, 2)

(1, 2) R(1,3) D(2,3) D(3,3) L(3,2) D(4,2)
Done!